BZOJ3629 聪明的燕姿

BZOJ3629 聪明的燕姿

唯一分解定律+约数和定理

搜索可能的质数，找出符合条件的答案

注意：不存在时，不要多大一个换行

#include<bits/stdc++.h>
using namespace std;
const int maxn = (1<<16)+5;
int prime[maxn], v[maxn], ans[maxn];
int m, cnt;
void primes()
{int n = 1<<16;for(int i = 2; i <= n; i++){if(!v[i]){ prime[++m] = i; v[i] = i; }for(int j = 1; j <= m; j++){if(prime[j] > v[i] || prime[j]*i > n) break;v[i*prime[j]] = prime[j];}}
}
bool check(int x)
{if(x == 1) return 0;for(int i = 2; i*i <= x; i++) if(x%i == 0) return 0;return 1;
}
void dfs(int now,int step,int num)
{if(now == 1){ans[++cnt] = num; return ;}if(check(now-1) && now-1 > prime[step]) ans[++cnt] = num*(now-1);for(int i = step+1; prime[i]*prime[i] <= now; i++){int tmp = 1, sum = 1;while(sum <= now){tmp *= prime[i]; sum += tmp;if(now%sum == 0) dfs(now/sum,i,num*tmp);}}return ;
}
int main()
{int n;primes();while(scanf("%d",&n) != EOF){cnt = 0;dfs(n,0,1);sort(ans+1,ans+cnt+1);printf("%d\n",cnt);for(int i = 1; i <= cnt; i++) printf("%d ",ans[i]);if(cnt) printf("\n");}return 0;
}