FZU 1851 – 组合数 [数学+组合数质因子]

Link

传送门

Problem

组合数 C(N,M)=N!/(M!*(N-M)!). 问题是求 C(N,M)中不同的素因子的个数

输入包含多组数据(数据组数<= 10),每组数据只有一行 2个正整数表示N和M (1 <= M <= N <= 1000000)

Analysis

非常好的一道数学题,受poj某道题题解的启发做出来的。

C(n,k)=n!/((n-k)!k!),把对应因子个数相减,我们就得到了c(n,k)分解的结果。看每个质因子的个数便可得到结果。

所以我们需要一种快速分解x!的方法。我们可以枚举所有x!中存在的素因子,对于每个素因子求个数的方式来分解。而对于一个素因子p,我们求在x!中的方法如下,1~x中有x/p个数可以被p整除,所以x!中至少有x/p个p。然后我们再看有多少个p^2。能被p^2整除的数一定能被p整除。所以我们先将1~x中不能被p整除的数刨除。再将剩下的数除以p。现在还能被p整除的数,原来一定包含p^2。而现在剩下的数是1~x/p,问题被我们转化为了一个子问题。(x/p)!中包含多少p。这样递归求解即可。

Code

#include <cstdio>
using namespace std;

const int maxn = 1024000;
bool checked[maxn] = {1, 1};
int pri[maxn], tot;
int n, m;

void getPrime() {
    for(int i = 2; i < maxn; ++i){
        if(!checked[i]) pri[tot++] = i;
        for(int j = 0; j < tot && pri[j] * i < maxn; ++j){
            checked[pri[j]*i] = true;
            if(!(i % pri[j])) break;
        }
    }
}

int solve(int x, int p) {
    return x ? x / p + solve(x / p, p) : 0;
}

int main() {
    getPrime();
    while(~scanf("%d%d", &n, &m), n||m) {
        int cnt = 0;
        for(int i = 0; pri[i] <= n; ++i) {
            int t = solve(n, pri[i]) - solve(m, pri[i]) - solve(n-m, pri[i]);
            if(t) ++cnt;
        }
        printf("%d\n", cnt);
    }
    return 0;
}

欢迎留言