洛谷4397 [JLOI2014]聪明的燕姿

题意

给出 $S$ ，求所有正约数之和 $=S$ 的数。

数据组数 $k\le 100$ ， $S\le 2\times 10^{9}$ 。

题解

约数和为：

$$\begin{matrix} \prod_{i=1}^n \end{matrix}\begin{matrix} \sum_{j=0}^{a_i} {p_i}^j \end{matrix}$$

可以先预处理 $\le \sqrt{S}$ 的质数进行搜索。用 $x$ 表示当前搜索的质数编号；$left$ 是剩下的需要分解的数（初值为 $S$）；$sum$ 是当前得到的数。得到答案有两种情况：

1. $left=1$ ，显然。
2. 如果 $left$ 可以分解为 $1$ 和没有搜索过的质数之和，那么 $sum\times (left-1)$ 可以作为答案，但不用退出函数。

注意答案个数较多，保存答案的数组 $ans[]$ 要开大一点。我就是因为没开够在洛谷和BZOJ上都A了，但LOJ上WA了。毕竟数组越界了答案就是玄学。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool ss[100005];
ll n,cnt,acnt,zs[20005],ans[200005];

inline void get_prime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    for (ll i=2;i<=100000;i++)
    {
        if (ss[i]) zs[++cnt]=i;
        for (ll j=1;j<=cnt && zs[j]*i<=100000;j++)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
}

inline bool is_prime(ll x)
{
    if (x==1) return 0;
    for (ll i=1;zs[i]*zs[i]<=x;i++)
    {
        if (x%zs[i]) continue;
        return 0;
    }
    return 1;
}

void dfs(ll x,ll left,ll sum)
{
    if (left==1)
    {
        ans[++acnt]=sum;
        return;
    }
    if (left>zs[x] && is_prime(left-1)) ans[++acnt]=sum*(left-1);
    for (ll i=x;zs[i]*zs[i]<=left;i++)
    {
        ll now=zs[i],nxt=zs[i]+1;
        for (;nxt<=left;now*=zs[i],nxt+=now)
        {
            if (left%nxt) continue; 
            dfs(i+1,left/nxt,sum*now);
        }
    }
}

int main()
{
    get_prime();
    while (~scanf("%lld",&n) && n)
    {
        acnt=0;
        dfs(1,n,1);
        printf("%lld\n",acnt);
        sort(ans+1,ans+acnt+1);
        for (ll i=1;i<=acnt;i++)
        {
            printf("%lld",ans[i]);
            if (i<acnt) printf(" ");
        }
        if (acnt) puts("");
    }
    return 0;
}