[JLOI2014]聪明的燕姿

发表于 | 分类于

题目

阴天傍晚车窗外
未来有一个人在等待
向左向右向前看
爱要拐几个弯才来
我遇见谁会有怎样的对白
我等的人他在多远的未来
我听见风来自地铁和人海
我排着队拿着爱的号码牌

城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字S，那么自己等的人手上的号码牌数字的所有正约数之和必定等于S
所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。
（莫名唱了起来= =）

INPUT

输入包含k组数据（k<=100）对于每组数据，输入包含一个号码牌S(S<=10^9)

OUTPUT

对于每组数据，输出有两行，第一行包含一个整数m，表示有m个等的人，第二行包含相应的m个数，表示所有等的人的号码牌。
注意：你输出的号码牌必须按照升序排列。

SAMPLE

INPUT

42

OUTPUT

3
20 26 41

解题报告

考试的时候，一看就知道A不了，打了个极其暴力的程序= =

1
2
3
4
5
6
7
8
9
10
11
inline void find(long long x){
	int ret(0);
	for(int i=2;i*i<=x;i++){
		if(x%i==0)
			ret+=i,ret+=x%i;
		if(i*i==x)
			ret-=i;
	}
	if(ret==s)
		ans++;
}

结果显然= =
正解则是个很神奇的东西
唯一分解定理：任何大于１的自然数，都可以唯一分解成有限个质数的乘积
即：n=p1^k1×p2^k2…×pa^ka
那么何不预处理出来一大圈质数，然后dfs出唯一分解式呢
n=p1^k1×p2^k2..×pa^ka
因数和即可表示成（p1+p1^2+…+p1^k1）…
那么我们就可以dfs了
（我实在不会数学啊QAQ）

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long L;
L s;
L prime[100001],num_prime(0);
bool flag[100001];
inline void play_table(){
    memset(flag,true,sizeof(flag));
    flag[0]=flag[1]=false;
    for(int i=2;i<100000;i++){
        if(flag[i])
            prime[++num_prime]=i;
        for(int j=1;j<=num_prime&&prime[j]*i<100000;j++){
            flag[i*prime[j]]=false;
            if(i%prime[j]==0)
                break;
        }
    }
}
L ans[1000001],top(0);
int ppp[4]={2,3,5,7};
/*inline int modular_exp(int a,int m,int n){
    if(m==0)
        return 1;
    if(m==1)
        return a%n;
    L w(modular_exp(a,m>>1,n));
    w=w*w%n;
    if(w&1)
        w=w*a%n;
    return w;
}
inline bool check(L x){
    if(x==2||x==3||x==5||x==7)
        return true;
    for(int i=0;i<4;i++)
        if(modular_exp(ppp[i],x,x)!=ppp[i])
            return false;
    return true;
}*/
inline bool check(L x){
    for(int i=1;prime[i]*prime[i]<=x;i++)
        if(x%prime[i]==0)
            return false;
    return true;
}
inline void dfs(L st,L pos,L now){
    if(st==1){
        ans[++top]=now;
        return;
    }
    if((st-1)>prime[pos]&&check(st-1))
        ans[++top]=now*(st-1);
    for(int i=pos+1;prime[i]*prime[i]<=st;i++){
        L t(1),al(1);
        for(int j=1;t<=st;j++){
            al*=prime[i];
            t+=al;
            if(st%t==0)
                dfs(st/t,i,now*al);
        }
    }
}
int main(){
    play_table();
    while(scanf("%lld",&s)==1){
        top=0;
        dfs(s,0,1);
        sort(ans+1,ans+top+1);
        printf("%lld\n",top);
        for(int i=1;i<top;i++)
            printf("%lld ",ans[i]);
        if(top!=0)
            printf("%lld\n",ans[top]);
    }
}

ps：本来想打Miller-Rabin的，然后就gg了QAQ