一本通1629聪明的燕姿

1629：聪明的燕姿

时间限制: 1000 ms 内存限制: 524288 KB

【题目描述】

城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。

可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 S

所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。

【输入】

输入包含

对于每组数据，输入包含一个号码牌

【输出】

对于每组数据，输出有两行，第一行包含一个整数

第二行包含相应的 m

注意：你输出的号码牌必须按照升序排列。

【输入样例】

【输出样例】

3
20 26 41

【提示】

数据范围与提示

对于 100% 的数据，

Ps：代码实现复杂度并不高

一本通1629聪明的燕姿-编程知识网

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{ll s=0;bool f=0;char ch=' ';while(!isdigit(ch)){f|=(ch=='-'); ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{if(x<0){putchar('-'); x=-x;}if(x<10){putchar(x+'0'); return;}write(x/10);putchar((x%10)+'0');return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=100005;
int Prim[N],P_Cnt;
bool Bo[N];
inline void Pre_Prime()
{Prim[P_Cnt=0]=0;int i,j;int B=100000;for(i=2;i<=B;i++){if(!Bo[i]){Prim[++P_Cnt]=i;}for(j=1;j<=P_Cnt&&Prim[j]*i<=B;j++){
//            printf("Shai %d*%d=%d\n",Prim[j],i,Prim[j]*i);Bo[Prim[j]*i]=1;if(i%Prim[j]==0) break;}}
//    printf("Cnt=%d\n",P_Cnt);
//    for(i=1;i<=P_Cnt;i++) Wl(Prim[i]);
//    exit(0);return;
}
int Num,Ans[N];
inline bool Check_Prime(int x)
{if(x<=100000) return (Bo[x])?(false):(true);int i;for(i=2;i*i<=x;i++) if(x%i==0){return false;}return true;
}
//(p1^0+p1^1+...+p1^a1)*(p2^0+p2^1+...+p2^a2)*...*(pn^0+pn^1+...+pn^an)
inline void dfs(int Last,int Shuz,int Sum)
{if(Sum==1){Ans[++*Ans]=Shuz; return;}if(Sum-1>Prim[Last]&&Check_Prime(Sum-1)){Ans[++*Ans]=Shuz*(Sum-1);}int i,j,t;for(i=Last+1;i<=P_Cnt&&Prim[i]*Prim[i]<=Sum;i++){t=Prim[i];for(j=t+1;j<=Sum;t*=Prim[i],j+=t) if(Sum%j==0){dfs(i,Shuz*t,Sum/j);}}return;
}
int main()
{Pre_Prime();while(~scanf("%d",&Num)){int i;*Ans=0;dfs(0,1,Num);sort(Ans+1,Ans+*Ans+1);*Ans=unique(Ans+1,Ans+*Ans+1)-Ans-1;Wl(*Ans);for(i=1;i<*Ans;i++){W(Ans[i]);}if(*Ans) Wl(Ans[*Ans]);}return 0;
}
/*
input
42
8359
output
3
20 26 41
0
*/