看到一个很大的数字的什么什么的余数就要想到唯一分解定律
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
void Getprimes(int n,vector<int>& p)
{int m=sqrt(n+0.5);for(int i=2;i<=m;i++){if(n%i==0){p.push_back(i);while(n%i==0) n/=i;}}if(n>1) p.push_back(n); //除不到一就说明剩下来的也是素因数
}
int bad[100000+5];
int main()
{int n,m;while(cin>>n>>m){vector<int> primes;Getprimes(m,primes);memset(bad,0,sizeof(bad));n--; //杨辉三角是从第0层开始数的，所以为(a+b)^(n-1); for(int i=0;i<primes.size();i++){int p=primes[i],min_e=0;int x=m;while(x%p==0) { x/=p;min_e++; } //m的primes[i]的系数int e=0;for(int k=1;k<n;k++) //因为e不清零所以还是保存着c(n,k-1)的指数{ //第一项还有最后一项系数都是1，不可能被整除，所以不用判断了 x=n-k+1; //n-k+1的primes[i]的系数while(x%p==0) { x/=p;e++; }x=k;while(x%p==0) { x/=p;e--; } //k的primes[i]的系数if(min_e>e) bad[k]=1; //（n-k+1)/(k*m)的系数>0代表可整除}}vector<int> ans;for(int k=1;k<n;k++)if(!bad[k]) ans.push_back(k+1); // 编号从1开始 cout<<ans.size()<<endl;if(!ans.empty()){cout<<ans[0];for(int i=1;i<ans.size();i++)cout<<' '<<ans[i];}cout<<endl;}return 0;
}