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
#include
#include
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);
