AcWing 1296. 聪明的燕姿
原题链接
中等
作者:
LQstoic
,
2022-02-23 19:09:00
,
所有人可见
,
阅读 152
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=50000;
bool st[N];//是否是质数
int primes[N],cnt=0;
int res[N],len;
int ans[N];
//筛选得到2~n之内的所有质数
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])//st[i]是质数
{
primes[cnt++]=i;
}
for(int j=0;primes[j]*i<=n;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0)//避免重复筛,得到i的最小质因子是primes[j]
{
break;
}
}
}
}
//判断x是否为质数,范围小于N的时候可以直接判断,大于N时用质因子判断
bool is_prime(int x)
{
if(x<N)
{
return !st[x];
}
for(int i=0;primes[i]<=x/primes[i];i++)
{
if(x%primes[i]==0)
{
return false;
}
}
return true;
}
void dfs(int last,int prod,int s)
{
if(s==1)
{
ans[len++]=prod;//prod这个数的约数之和满足条件
return ;
}
if(s-1>(last<0?1:primes[last]) && is_prime(s-1))
{
ans[len++]=prod*(s-1);
}
for(int i=last+1;primes[i]<=s/primes[i];i++)
{
int p=primes[i];
//j为1+p+p^2+p^3....
//t为p->p^2->p^3
for(int j=1+p,t=p;j<=s;t*=p,j+=t)
{
if(s%j==0)
{
dfs(i,prod*t,s/j);
}
}
}
}
int main()
{
get_primes(N-1);
int s;
while(cin>>s)
{
len=0;
dfs(-1,1,s);
cout<<len<<endl;
if(len)
{
sort(ans,ans+len);
for(int i=0;i<len;i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
}
return 0;
}