「JLOI2014」聪明的燕姿

发表于 | 分类于 | | 浏览量： 次

大法师出奇迹！

传送门

洛谷P4397

BZOJ3629

题解

对于一个数$X$对它分解质因数：

则有：

所以可先把所有小于$\sqrt{S}$质数筛出来。

然后暴力搜索每个因子的个数。

最后那个大于$\sqrt{S}$的质因子，暴力判一下即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
int S,p[4700],tot,ans[10000000];bool vis[45000];
inline void make_p()
{
	vis[0]=vis[1]=true;
	for(int i=2;i<=45000;i++)
	{
		if(!vis[i]) p[++p[0]]=i;
		for(int j=1;j<=p[0]&&p[j]*i<=45000;j++)
		{
			vis[i*p[j]]=true;
			if(i%p[j]==0) break;
		}
	}
}
inline bool IsPrime(int x)
{
	for(int i=2;i*i<=x;i+=(i&1)+1)
		if(x%i==0)
			return false;
	return true;
}
void DFS(int pn,int SN,int Num)
{
	if(SN==1)
	{
		ans[++tot]=Num;
		return;
	}
	if(SN>p[pn]&&IsPrime(SN-1)) ans[++tot]=Num*(SN-1);   //特判
	for(int i=pn;p[i]*p[i]<=SN;i++)        //枚举因子
	{
		LL t=p[i],sum=p[i]+1;
		for(;sum<=SN;t*=p[i],sum+=t)       //枚举因子个数
			if(SN%sum==0) 
				DFS(i+1,SN/sum,Num*t);
	}
}
int main()
{
	make_p();
	while(scanf("%d",&S)==1)
	{
		tot=0;DFS(1,S,1);
		printf("%d\n",tot);
		sort(ans+1,ans+1+tot);
		for(int i=1;i<=tot;i++)
			printf("%d%c",ans[i],i==tot?'\n':' ');
	}
	return 0;
}