题意：整个式子的和可以 化简为 sigma (C(n-1,i-1)*ai)
思路：只要判断C(n-1,i-1)能否被 m整除即可。
做法是先分解m的质因数，，然后计算1！~(n-1)! 包含m的质因数的个数
C（n-1,i-1） = (n-1)!/((i-1)!*(n-i)!)
只要判断 剩下的质因数的个数是否大于等于m的任一个质因数的个数即可
<pre name="code" class="cpp">#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<string>#include<algorithm>#include<queue>#include<cmath>using namespace std;typedef long long LL;const int maxp = 40000 + 10;const int maxn = 100000 + 10;int n,m;bool isPrime[maxp];vector<int> ret,prime,hp,cnt,tmp;vector<int> g[maxn];void getPrime(){memset(isPrime,true,sizeof isPrime);for(int i=2;i<maxp;i++){if(isPrime[i]){prime.push_back(i);for(int j=i+i;j<maxp;j+=i){isPrime[j]=false;}}}}void getDigit(){int tk=m;for(int i=0;i<prime.size()&&prime[i]*prime[i]<=tk;i++){if(tk%prime[i]==0){int k=0;hp.push_back(prime[i]);while(tk%prime[i]==0){tk/=prime[i];k++;}cnt.push_back(k);}}if(tk>1){hp.push_back(tk);cnt.push_back(1);}}void init(){cnt.clear();hp.clear();ret.clear();getDigit();for(int i=0;i<=n-1;i++) g[i].clear();for(int i=0;i<=n-1;i++){for(int j=0;j<hp.size();j++){int d=0,t=i;while(t){d+=t/hp[j];t/=hp[j];}g[i].push_back(d);}}}void solve(){bool miden = false;for(int i=2;i<=(n-1)/2+1;i++){bool flag=true;for(int j=0;j<hp.size();j++){int d=g[n-1][j]-g[i-1][j]-g[n-i][j];if(d<cnt[j]){flag=false;break;}}if(flag){ret.push_back(i);if(i==(n-1)/2+1&&(n&1))miden=true;}}tmp.clear();tmp=ret;if(n&1){int i;if(miden) i=tmp.size()-2;else i=tmp.size()-1;for(;i>=0;i–){ret.push_back(n+1-tmp[i]);}}else{for(int i=tmp.size()-1;i>=0;i–){ret.push_back(n+1-tmp[i]);}}printf("%d\n",ret.size());if(ret.size()){printf("%d",ret[0]);for(int i=1;i<ret.size();i++)printf(" %d",ret[i]);}puts("");}int main(){getPrime();while(~scanf("%d%d",&n,&m)){init();solve();}return 0;}
地球仍然转重，世间依旧善变，而我永远爱你。
