「BZOJ3629」[JLOI2014] 聪明的燕姿
Description
阴天傍晚车窗外
未来有一个人在等待
向左向右向前看
爱要拐几个弯才来
我遇见谁会有怎样的对白
我等的人他在多远的未来
我听见风来自地铁和人海
我排着队拿着爱的号码牌
城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字S，那么自己等的人手上的号码牌数字的所有正约数之和必定等于S。
所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。
Input
输入包含k组数据（k<=100）
对于每组数据，输入包含一个号码牌S
Output
对于每组数据，输出有两行，第一行包含一个整数m，表示有m个等的人，第二行包含相应的m个数，表示所有等的人的号码牌。注意：你输出的号码牌必须按照升序排列。
Sample Input
42
Sample Output
3
20 26 41
20 26 41
HINT
对于100%的数据，有S<=2*109
题解
我们一起膜拜wulala吧
http://wulala.logdown.com/posts/207881-stefanie-jloi-2014-smart
|
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 |
#include<iostream> #include<cmath> #include<algorithm> #include<cstdio> #include<cstring> #define ll long long using namespace std; int s,sqrts,top,cnt; int ans[100000],p[50005]; bool mark[50005]; void getpri() { for(int i=2;i<=50000;i++) { if(!mark[i])p[++cnt]=i; for(int j=1;p[j]*i<=50000;j++) { mark[p[j]*i]=1; if(i%p[j]==0)break; } } } bool jud(int x) { if(x<=50000)return (!mark[x]); else { int t=sqrt(x); for(int i=1;p[i]<=t;i++) if(x%p[i]==0)return 0; return 1; } } void dfs(int last,ll tot,int sum) { if(tot==1){ans[++top]=sum;return;} if(tot-1>sqrts&&jud(tot-1))ans[++top]=sum*(tot-1); for(int i=last+1;p[i]<=sqrts;i++) { ll tmp=1,t=p[i]; for(int j=1;tmp+t<=tot;j++) { tmp+=t; if(tot%tmp==0) dfs(i,tot/tmp,sum*t); t*=p[i]; } } } int main() { getpri(); while(scanf("%d",&s)!=EOF) { top=0;sqrts=sqrt(s); dfs(0,s,1); printf("%d\n",top); sort(ans+1,ans+top+1); for(int i=1;i<top;i++) printf("%d ",ans[i]); if(top)printf("%d\n",ans[top]); } return 0; } |
倒着枚举质数出奇迹 ORZ %%%