UVa1635 - Irrelevant Elements（质因数分解）

Input 

1n100 000

2m10⁹

Output 

Sample Input 

3 2

Sample Output 

1
2

题意：整个式子的和可以  化简为  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的任一个质因数的个数即可

#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(){
    //freopen("test.txt","r",stdin);
    getPrime();
    while(~scanf("%d%d",&n,&m)){
        init();
        solve();
    }
    return 0;
}

UVa1635 - Irrelevant Elements（质因数分解）

原文：http://blog.csdn.net/mowayao/article/details/38930127