组合素数

组合素数 - nefu119

题意：求解C(2n,n)恰好被p整除多少次

由组合数公式可以将其转化为：
(2 * n)!/(n! * n!)

则将题目转化为求解分子关于q的幂，减去分子关于q的幂
用公式

• n!的素因子分解中素数p的幂为[n/p]+[n/p^2]+[n/p^3]...0 (p^t <= n)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
typedef long long ll;
int main()
{
    int cas;
    cin >> cas;
    while(cas--)
    {
        ll n,p;
        ll ans = 0;
        cin >> n >> p;
        ll tmpp = p;
        while(tmpp <= n)
        {
            ans += n/tmpp;
            tmpp *= p;
        }

        ll ans1 = 0;
        tmpp = p;
        while(tmpp <= 2*n)
        {
            ans1 += 2*n/tmpp;
            tmpp *= p;
        }
        cout << ans1-2*ans << endl;
    }
    return 0;
}