1635 - Irrelevant Elements

根据递推公式，（指数也可以利用这个公式）    由刘汝佳所言，只需判断二项式展开式的每个项的系数是否是m的倍数即可，由唯一分解定律，只要指数大于m的分解项指数，就可以除尽这一项；    但是要注意，并不是每个项都可以被唯一分解完全的。

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[42000+5],max_cnt,c[100000+6],a[100000+5],prime[100000+5],e[100000+5];
vector<int> primes;
void add_primes() {        //打出素数表。
    int m = sqrt(32000+0.5);
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=m;i++) if(!vis[i])
    for(int j=i*i;j<=32000;j+=i) vis[i] = 1;
    for(int i=2;i<=32000;i++)
        primes.push_back(i);
}
void add_factors(int n) {
    max_cnt=0;
    for(int i=0;i<primes.size();i++){
        if(n%primes[i]==0) prime[max_cnt++]=primes[i];
        while(n%primes[i]==0) {
            n/=primes[i];
            e[max_cnt-1]++;
        }
        if(n==1) break;//提前推出，节省时间。
    }
    if(n>1) { prime[max_cnt]=n; e[max_cnt++]=1; } //必不可少
}
int main() {
    add_primes();
    while(scanf("%d%d",&n,&m)!=EOF) {
        memset(c,0,sizeof(c));
        memset(e,0,sizeof(e));
        add_factors(m);
        n--;
        for(int i=0;i<max_cnt;i++) {
            int max_e=0;   //当前项系数情况。
            for(int k=1;k<=n;k++) {
                int ans = n-k+1;
                while(ans%prime[i]==0) {
                    ans/=prime[i];
                    max_e++;
                }
                ans = k;
                while(ans%prime[i]==0) {
                    ans/=prime[i];
                    max_e--;
                }
                if(max_e<e[i]) c[k] = 1;
            }
        }
        int kase = 0;
        for(int i=1;i<=n;i++){
            if(!c[i]) a[kase++]=i+1;
            }
        if(kase){
            printf("%d\n",kase);
            for(int i=0;i<kase;i++)
                if(!i) printf("%d",a[i]);
                else printf(" %d",a[i]);
            printf("\n");
        }
        else printf("0\n\n");
    }
    return 0;
}

1635 - Irrelevant Elements

原文：http://blog.csdn.net/weizhuwyzc000/article/details/44594759