聪明的燕姿题解

· · 题解

题意

给出一个数 S ,求约数和等于 S 的数。

分析

约数和定理

我们知道，求一个数 x 的约数和，可以先将它分解质因数，得到

\large x=\prod_{i=1}^kp_i^{a_i} $$\prod_{i=1}^k(\sum_{j=0}^{a_i}p_i^j) $$ 那么这题就是将此反推会去求 $x$ 。 定义一个数 $a$ 满足 $a=\sum_{i=0}^b p^i=(1+p+p^2+\dots+p^b)$ ，这里 $b$ 没有限定， $p$ 为任意质数，我们把 $a$ 叫做“质数和”， $p^b$ 叫做 $a$ 的最大加数（自己瞎定义的，方便下面说明）。 **那么 $S$ 就是几个质数和的乘积，我们就要把 $S$ 分解开来， $x$ 就等于这些质数和的最大加数的乘积，注意这样分解可能不止一种分解方法，不是唯一分解的。** ## 预处理 **我们可以先处理出 $1$ 到 $\sqrt S$ 的质数，用于预处理出 $1$ 到 $S$ 的质数和。** 这里处理出来的质数和不是所有的质数和，而是 $p\leq\sqrt S$ 且质数和小于等于 $S$ 的质数和。 那 $\sqrt S<p\leq S$ 的质数和呢？ 我们发现满足此条件的 $p^2>S$ 所以只会出现形同 $1+p$ 这样质数和小于等于 $S$ ，而 $1+p$ 又大于 $\sqrt S$ ，在分解中只会出现一次，所以分解到最后可以直接 $O(\sqrt S)$ 判断是否为这种质数和就好了，无需预处理。 **为了最后得出 $x$ ，我们用 $map$ 存这些质数和，关键字是质数和，关键字的值是这个质数和的最大加数。** 因为一个数可能是 $p$ 不同的质数和，如 $31=1+2+4+8+16=1+5+25$ 所以**关键字的值要用 $vector$ 存。** ## 分解 $S

预处理出质数和，我们再枚举 S 的约数，把同为 S 约数和质数和的数拎出来，就可以递归分解 S 了。

把 S 分解成质数和的乘积，最后统计答案就好了。

这里有一个小细节，统计答案时不是要把最大加数都乘起来吗，这里所以的最大加数都要相互互质，不然就会出现 (1+p+p^2)\cdot(1+p+p^2+p^3)=S 且 p 相同情况，这根本不符合约数和定理。

代码

#include<bits/stdc++.h>

using namespace std;

long long gcd(long long x,long long y){return y?gcd(y,x%y):x;}

//prime 筛质数 
int prime[10000]={0},pn=0;
void getprime()
{
    bool is_prime[50000]={0};
    for(int i=2;i<=50000;i++)
    {
        if(!is_prime[i]) prime[++pn]=i;
        for(int j=1;j<=pn&&prime[j]*i<=50000;j++)
        {
            is_prime[prime[j]*i]=1;
            if(!(i%prime[j])) break;
        }
    }
}
//isprime 判断质数 
bool isprime(long long x)
{
    for(int i=2;i<=sqrt(x);i++)
        if(!(x%i)) return 0;
    return 1;
}

//Map 用Map记录下可以分成 1+p+p^2... 的数 
map<long long,vector<long long> > Map;
void getMap()
{
    for(long long i=1,sum,power;i<=pn;i++)
    {
        power=prime[i];
        sum=1+power;
        while(sum<=2e9)
        {
            Map[sum].push_back(power);
            power*=prime[i];
            sum+=power;
        }
    }
}

//ans
long long ans[100000]={0},ansn=0,final_ans[100000]={0};

//div div是S的约数，同时这个约数要满足可以分成 1+p+p^2... 
long long S,sqrt_S;
int S_div[50000]={0},dn=0;
void getdiv()
{
    for(long long i=1;i<=sqrt_S;i++)
    {
        if(!(S%i))
        {
            if(Map.find(i)!=Map.end()) S_div[++dn]=i;
            if(i!=S/i&&Map.find(S/i)!=Map.end()) S_div[++dn]=S/i;
        }
    }
    sort(S_div+1,S_div+1+dn);
}

//put q into ans
vector<int> q;
void putout(long long prod,int p)
{
    if(p>=q.size())
    {
        return (void)(ans[++ansn]=prod);
    }
    for(int i=0;i<Map[q[p]].size();i++)
        if(gcd(prod,Map[q[p]][i])==1)
            putout(prod*Map[q[p]][i],p+1);
}

//q （ q 为队列，因为有些数会被分成不同的 1+p+p^2... 所以要加入队列中用 putout 遍历一遍）
void getq(int now_S,int now_div)
{
    if(now_S==1) return putout(1,0);
    for(int i=now_div;i<=dn;i++)
    {
        if(now_S<S_div[i]) break;
        if(now_S%S_div[i]==0)
        {
            q.push_back(S_div[i]);
            getq(now_S/S_div[i],i+1);
            q.pop_back();
        }
    }
    if(now_S>sqrt_S&&isprime(now_S-1)) putout(now_S-1,0);
}

int main()
{
    getprime();
    getMap();

    while(cin>>S)
    {
        memset(ans,0,sizeof(ans));
        memset(S_div,0,sizeof(S_div));
        dn=0;
        ansn=0;
        sqrt_S=sqrt(S);
        getdiv();

        getq(S,1);

        sort(ans+1,ans+1+ansn); //将答案排序 
        long long *p=unique(ans+1,ans+1+ansn); //去重 
        ansn=0;
        for(long long *i=&ans[1];i!=p;i++,ansn++); //统计个数 
        cout<<ansn<<endl;
        for(long long *i=&ans[1];i!=p;i++) //输出 
        {
            cout<<*i;
            if(i+1!=p) cout<<" ";
            else cout<<endl;
        }
    }
}