legendre第一定理？

Legendre定理：

設n為一個正整數，那么在n!的標準素因子分解式中，素數p的最高次項為L_{p}(n!)，則

L_{p}(n!)=\sum_{k\geq1} \left [ \frac{n}{p^k} \right ]

當模數不為素數，且不方便使用CRT進行合并時，可以考慮對組合數分解質因數，由于組合數可以寫為一個階乘除以兩個階乘的形式，可以對這三個階乘分別分解質因數，然后使用指數的減法，得到最后組合數的標準分解。

證明我就不在這里細說了，反正這個定理可以讓我們快速求出p的指數。

下面是例題。

題目描述：

求方程x_{1}+x_2+......x_k=n的非負整數解的組數n,k≤100,000，答案對20080814取模輸入：

僅一行，包含兩個正整數n,k。

輸出：一個整數，表示方程不同解的個數，這個數可能很大，你只需輸出mod 20080814 的結果。

樣例輸入:

1 1

樣例輸出：

1

思路分析：

利用隔板法，答案為\LARGE C_{n+1}^{k-1}

由于20080814=2*13*772339（3個均為質因數），故可以用CRT。

也可以用Legendre定理分解階乘的質因數。

但是此題的輸入有坑，n，k需要特殊處理，詳見代碼。

代碼實現：

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

#define ll long long

ll n,m,p[200005],w[200005],k,ans=1;

bool v[200005];

ll olsf()//歐拉篩法求素數

{for(ll i=2;i<=n+1;i++) { if(!v[i])

{ k++; p[k]=i; v[i] = 1; }

for(ll j=1;j<=k&&p[j]*i<=n+1;j++)

{ v[i*p[j]]=1;if(i%p[j]==0)

break; }

}

}

ll qkpow(ll x,ll y)//快速冪不解釋

{

ll ans=1;

while(y)

{

if(y&1)

ans=(ans*x)%20080814;

x=(x*x)%20080814;

y/=2;

}

return ans%20080814;

}

int main()

{

scanf("%lld%lld",&m,&n);

n=n+m-1;

m--;

olsf();

for(ll i=1;i<=k;i++)//求分子的分解

for(ll j=p[i];j<=n;j*=p[i])

w[i]+=n/j;

for(ll i=1;i<=k;i++)//求分母的分解

for(ll j=p[i];j<=m;j*=p[i])

w[i]-=m/j;

for(ll i=1;i<=k;i++)

for(ll j=p[i];j<=n-m;j*=p[i])

w[i]-=(n-m)/j;

for(ll i=1;i<=k;i++)

ans=(ans*qkpow(p[i],w[i]))%20080814;

printf("%lld",ans);