同对m和n的每一项用唯一分解定理，比较次数，比m大则m是i的约数，否则不是，是约数，则无关
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <vector> using namespace std; const int maxn=100000+100; int num[maxn][3]; int vis[maxn]; int c[maxn]; int cnt; int n,m; void init() { memset(num,0,sizeof(num)); memset(vis,0,sizeof(vis)); memset(c,0,sizeof(c)); } void factor()//m的唯一分解定理 { cnt=0; for(int i=2;i*i<=m;i++) { if(m%i==0) { cnt++; num[cnt][0]=i; while(m%i==0) { num[cnt][1]++; m=m/i; } } } if(m>1) { cnt++; num[cnt][0]=m; num[cnt][1]=1; } } bool check(int i,int n)//前一项已经对C进行过计算，所以只算者这一项的就可以 { int y=(n-1)-i+1; int x=i; for(int j=1;j<=cnt;j++) { while(y%num[j][0]==0) { c[j]++; y=y/num[j][0]; } while(x%num[j][0]==0) { c[j]--; x=x/num[j][0]; } } for(int j=1;j<=cnt;j++)//次数必须大于m的同质数项的次数 if(c[j]<num[j][1]) return 0; return 1; } int main() { while(~scanf("%d%d",&n,&m)) { init(); factor(); int ans=0; for(int i=1;i<n-1;i++)//注意有n项，但是组合数计算时时C(0,n-1),C(1,n-1)......C(n-1,n-1); { if(check(i,n)) { ans++; vis[i]=1; } } printf("%d\n",ans); int first=0; for(int i=1;i<n-1;i++) if(vis[i]) { if(!first) first=1; else printf(" "); printf("%d",i+1); } printf("\n"); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/8408879.html
