/** 题目:Irrelevant Elements UVA - 1635 链接:https://vjudge.net/problem/UVA-1635 题意:給定n,m;題意抽象成(a+b)^(n-1)按照二次项分布后每个系数的值按照位置分别为c1,c2,c3...; 如果ci%m==0; 那么输出这个位置。 思路:已知n,计算系数的方法:c(n,m) = (n-m+1)/m*c(n,m-1) ;由于c(n,m-1)%m不一定等于0.所以要先乘。 由于n达到了1e5,所以如果算结果是不可行的。一边乘一边对m(题目的m)取模也是不行的。因为有除法存在,且不一定都有逆元。 所以采用唯一分解定理来处理。 对每一个系数判断在m这个数的所有素因子都可以>=;这样就可以包含它。注意特殊情况,m=1 或者n=1的时候处理方式。 求每一个系数的素因子个数也是可以用c(n,m) = (n-m+1)/m*c(n,m-1)这个公式来递推。 */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include <vector> #include <cmath> using namespace std; typedef long long ll; typedef unsigned long long ull; const int inf = 0x3f3f3f3f; const int maxn = 1e5+100; const int e9 = 1e9; const double eps = 1e-6; int prime[maxn], pz; int e[104]; int p[104], z; int c[104]; int a[maxn]; void init() { int N = sqrt(e9+0.5); for(int i = 2; i<=N; i++){ if(prime[i]==0){ for(int j = i*i; j <= N; j+=i){ prime[j] = 1; } } } pz = 0; for(int i = 2; i <= N; i++){ if(prime[i]==0){ prime[pz++] = i; } } //cout<<"pz = "<<pz<<endl; } void add_factor(int x,int add) { for(int i = 0; i < z&&x!=1; i++){ while(x%p[i]==0){ e[i]+=add; x/=p[i]; } } } bool ok() { for(int i = 0; i < z; i++){ if(e[i]>0) return false; } return true; } int main() { int n, m; init(); while(scanf("%d%d",&n,&m)==2) { z = 0; memset(e, 0, sizeof e); for(int i = 0; i < pz&&prime[i]*prime[i]<=m; i++){ if(m%prime[i]==0){ while(m%prime[i]==0){ e[z]++; m /= prime[i]; } p[z++] = prime[i]; } } if(m>1){ e[z] = 1; p[z++] = m; } n = n-1; int cnt = 0; for(int i = 1; i <= n; i++){ add_factor(n-i+1,-1);//n-m+1 add_factor(i,1);// /m if(ok()){ a[cnt++] = i; } } printf("%d ",cnt); for(int i = 0; i < cnt; i++){ printf("%d%s",a[i]+1,i==cnt-1?" ":" "); } if(cnt==0){///小坑,哪怕结果为0,也要有一个换行。 printf(" "); } } return 0; }