Project Euler 231

题目

The prime factorisation of binomial coefficients

The binomial coefficient \(\displaystyle \binom {10} 3 = 120\).

\(120 = 2^3 \times 3 \times 5 = 2 \times 2 \times 2 \times 3 \times 5\), and \(2 + 2 + 2 + 3 + 5 = 14\).

So the sum of the terms in the prime factorisation of \(\displaystyle \binom {10} 3\) is \(14\).

Find the sum of the terms in the prime factorisation of \(\displaystyle \binom {20\,000\,000} {15\,000\,000}\).

解决方案

组合数\(\dbinom{n}{m}\)的定义为\(\dfrac{n!}{(n-m)!m!}\)。因此，求一个质因数\(p\)在组合数的次数，本质上是求在阶乘中出现的次数。

设\(f(n, p)\)是质因子\(p\)在\(n!\)中的次数，那么\(f(n,p)=\left\lfloor\dfrac{n}{p}\right\rfloor+\left\lfloor\dfrac{n}{p^2}\right\rfloor+\left\lfloor\dfrac{n}{p^3}\right\rfloor+\dots\)，每一项分别表示\(1\sim n\)中有多少个数是\(p,p^2,p^3\dots\)的倍数。

因此根据组合数的定义式，\(\dbinom{n}{m}\)的质因子\(p\)出现的次数为\(f(n,p)-f(m,p)-f(n-m,p)\)。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20000000,M=15000000;
int v[N+4],pr[N/10],m=0;
ll f(ll n,ll p){
    ll ans=0;
    for(;n;n/=p)
        ans+=n/p;
    return ans;
}
int main(){
    for(int i=2;i<=N;i++){
        if(v[i]==0){
            v[i]=i;pr[++m]=i;
        }
        for(int j=1;j<=m;j++){
            if(pr[j]>v[i]||pr[j]>N/i) break;
            v[i*pr[j]]=pr[j];
        }
    }
    ll ans=0;
    for(int i=1;i<=m;i++){
        int p=pr[i];
        ans+=(f(N,p)-f(M,p)-f(N-M,p))*p;
    }
    printf("%lld\n",ans);
}