暴力出奇迹
#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
",Num);
if (Num){
for (int i=1; i<=Num; i++) printf("%d ",ANS[i]);
printf("
");
}
}
return 0;
}