「JLOI2014」聪明的燕姿 - 约数和 | Bill Yang's Blog

「JLOI2014」聪明的燕姿 - 约数和

题目大意

求出所有约数和为$n$的值$x$


初步想法

枚举$x$验证是否约数和为$n$。
求约数和可以使用约数和公式:

用线性筛预处理$O(\sqrt{n})$内的素数,这么麻烦才能拿到30分。


算法优化

稍加思考就可以想到100%的算法。
显然枚举$x$效率太低,我们能否将$x$计算出来?
由公式:

$n$是一些数的乘积,故可以直接对$n$进行分解。
枚举质数以及其幂,然后递归。
每层Dfs时间复杂度约为$O(\sqrt{Remain})$,$Remain$是尚未分解的$n$的约数乘积。


代码

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
55
56
57
58
59
60
61
62
63
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const long long Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
bool vst[100005];
long long n,Prime[100005],cnt=0,ans[100005];
void Prime_Table(int n) {
for(int i=2; i<=n; i++) {
if(!vst[i])Prime[++cnt]=i;
for(int j=1; j<=cnt&&Prime[j]*i<=n; j++) {
vst[Prime[j]*i]=1;
if(i%Prime[j]==0)break;
}
}
}
bool Check_Prime(long long n) {
if(n==1)return 0;
for(int i=1; i<=cnt&&Prime[i]<=sqrt(n); i++)
if(n%Prime[i]==0)return 0;
return 1;
}
void Dfs(long long Now,int Depth,long long Remain) {
if(Remain==1) {
ans[++ans[0]]=Now;
return;
}
if(Remain-1>=Prime[Depth]&&Check_Prime(Remain-1))ans[++ans[0]]=Now*(Remain-1);
for(int i=Depth; i<=cnt&&Prime[i]<=sqrt(Remain); i++) {
int sum=1+Prime[i],Pow=Prime[i];
for(; sum<=Remain; Pow*=Prime[i],sum+=Pow)
if(Remain%sum==0)Dfs(Now*Pow,i+1,Remain/sum);
}
}
int main() {
Prime_Table(100000);
while(scanf("%lld",&n)!=EOF) {
ans[0]=0;
Dfs(1,1,n);
sort(ans+1,ans+ans[0]+1);
printf("%lld\n",ans[0]);
for(int i=1; i<=ans[0]; i++)printf("%lld%c",ans[i],i==ans[0]?'\n':' ');
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%