AcWing算法提高课 分解质因数求组合数

模板：

int primes[N],cnt;
bool not_prime[N];
void Init()
{
    for(int i=2;i<N;i++)
    {
        if(!not_prime[i])
        {
            primes[cnt++]=i;
            for(int j=i+i;j<N;j+=i)
            {
                not_prime[j]=true;
            }
        }
    }
}


LL Get(LL n,LL p)//n!中因子p的个数
{
    LL s=0;
    LL op=p;
    while(p<=n)
    {
        s+=n/p;
        p*=op;//对p^k处理
    }
    return s;
}
int sum[N];//分解质因数的数量

int C(int n,int k,int r[N])
{
    memset(sum,0,sizeof(sum));
    for(int i=0;i<cnt;i++)//枚举质因数
    {
        sum[i]=Get(n,primes[i])-Get(k,primes[i])-Get(n-k,primes[i]);
    }
    //此时已经获得了组合数的全部质因数，乘起来就是结果
}

分解质因数求组合数结合高精度例题：

https://www.acwing.com/problem/content/1317/