暴力出奇迹
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- const int Max=2e9;
- int lim,cnt,Num,ANS[100005],isprime[100005],prime[100005];
- void Pre_prime(){
- for (int i=2; i<=sqrt(Max); i++){
- if (!isprime[i]) prime[++cnt]=i;
- for (int j=1; j<=cnt && i*prime[j]<=sqrt(Max); j++){
- isprime[i*prime[j]]=1;
- if (i%prime[j]==0) break;
- }
- }
- }
- int calc(int x){
- if (x==1) return 0;
- if (x<=(int)sqrt(Max)) return 1-isprime[x];
- for (int i=1; i<=cnt && prime[i]<x; i++)
- if (x%prime[i]==0) return 0;
- return 1;
- }
- void dfs(int t,int S,int now){
- if (S==1){
- ANS[++Num]=now;
- return;
- }
- if (S-1>lim && calc(S-1)) ANS[++Num]=now*(S-1);
- for (int T=t+1; prime[T]<=lim && T<=cnt; T++)
- for (long long P=prime[T],F=1+prime[T]; F<=S; P*=prime[T],F+=P)
- if (S%F==0) dfs(T,S/F,now*P);
- }
- int main(){
- Pre_prime();
- int S;
- while (scanf("%d",&S)!=EOF){
- lim=(int)sqrt(S);
- int f=1;
- for (int i=1; i<=cnt; i++) if ((S-1)%prime[i]==0) f=0;
- Num=0;
- dfs(0,S,1);
- if (f) ANS[++Num]=S-1;
- sort(ANS+1,ANS+Num+1);
- Num=unique(ANS+1,ANS+Num+1)-ANS-1;
- printf("%d\n",Num);
- if (Num){
- for (int i=1; i<=Num; i++) printf("%d",ANS[i]);
- printf("\n");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2824944.html