[补档][JLOI 2017]聪明的燕姿

[NOI 2008]假面舞会

题目

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

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

INPUT

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

OUTPUT

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

SAMPLE

INPUT

42

OUTPUT

3
20 26 41

解题报告

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

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

View Code

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

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 typedef long long L;
 7 L s;
 8 L prime[100001],num_prime(0);
 9 bool flag[100001];
10 inline void play_table(){
11     memset(flag,true,sizeof(flag));
12     flag[0]=flag[1]=false;
13     for(int i=2;i<100000;i++){
14         if(flag[i])
15             prime[++num_prime]=i;
16         for(int j=1;j<=num_prime&&prime[j]*i<100000;j++){
17             flag[i*prime[j]]=false;
18             if(i%prime[j]==0)
19                 break;
20         }
21     }
22 }
23 L ans[1000001],top(0);
24 int ppp[4]={2,3,5,7};
25 /*inline int modular_exp(int a,int m,int n){
26     if(m==0)
27         return 1;
28     if(m==1)
29         return a%n;
30     L w(modular_exp(a,m>>1,n));
31     w=w*w%n;
32     if(w&1)
33         w=w*a%n;
34     return w;
35 }
36 inline bool check(L x){
37     if(x==2||x==3||x==5||x==7)
38         return true;
39     for(int i=0;i<4;i++)
40         if(modular_exp(ppp[i],x,x)!=ppp[i])
41             return false;
42     return true;
43 }*/
44 inline bool check(L x){
45     for(int i=1;prime[i]*prime[i]<=x;i++)
46         if(x%prime[i]==0)
47             return false;
48     return true;
49 }
50 inline void dfs(L st,L pos,L now){
51     if(st==1){
52         ans[++top]=now;
53         return;
54     }
55     if((st-1)>prime[pos]&&check(st-1))
56         ans[++top]=now*(st-1);
57     for(int i=pos+1;prime[i]*prime[i]<=st;i++){
58         L t(1),al(1);
59         for(int j=1;t<=st;j++){
60             al*=prime[i];
61             t+=al;
62             if(st%t==0)
63                 dfs(st/t,i,now*al);
64         }
65     }
66 }
67 int main(){
68     play_table();
69     while(scanf("%lld",&s)==1){
70         top=0;
71         dfs(s,0,1);
72         sort(ans+1,ans+top+1);
73         printf("%lld
",top);
74         for(int i=1;i<top;i++)
75             printf("%lld ",ans[i]);
76         if(top!=0)
77             printf("%lld
",ans[top]);
78     }
79 }

View Code

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