UVA 1635 Irrelevant Elements（唯一分解定理，杨辉三角）

// // main.cpp // Richard // // Created by 邵金杰 on 16/8/16. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int maxn=100000+10; int primes[maxn],bad[maxn],e[maxn],result[maxn]; int p_cnt=0; void get_prime(int n) { p_cnt=0; int m=floor(sqrt(n)+0.5); for(int i=2;i<=m;i++) { if(n%i==0) primes[p_cnt++]=i; while(n%i==0) {e[p_cnt-1]++;n/=i;} } if(n>1) { primes[p_cnt]=n; e[p_cnt++]=1; } } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(primes,0,sizeof(primes)); memset(bad,0,sizeof(bad)); memset(e,0,sizeof(e)); memset(result,0,sizeof(result)); n--; get_prime(m); for(int i=0;i<p_cnt;i++) { int p=primes[i]; int need=e[i]; int min_e=0; for(int k=1;k<=n/2;k++) { int x=n-k+1; while(x%p==0) min_e++,x/=p; x=k; while(x%p==0) min_e--,x/=p; if(min_e<need) bad[k]=1; } } int cnt=0; for(int k=1;k<=n/2;k++) { if(!bad[k]) result[cnt++]=k; } if(cnt) { int size=cnt-1; if(result[size]*2==n) size--; for(int i=size;i>=0;i--) result[cnt++]=n-result[i]; printf("%d\n",cnt); printf("%d",result[0]+1); for(int i=1;i<cnt;i++) printf(" %d",result[i]+1); } else puts("0"); printf("\n"); } return 0; }