题目链接

当p是质数时,有如下定理

Lucas定理： $ C_{a}^{b} \equiv C_{a \bmod p}^{b \bmod p} \times C_{a/p}^{b/p} \pmod{p} $

易错：res = (ll)res * i % p * qmi(j, p - 2) % p;

这行代码不能写成 res = (ll)res * i % p / j % p ！！！！

#include <iostream>
using namespace std;

typedef long long ll;
ll n, a, b, p;

int qmi(int a, int m){
    int res = 1;
    while (m){
        if (m & 1) res = (ll)res * a % p;
        a = (ll)a * a % p;
        m >>= 1;
    }

    return res;
}

// C()函数直接暴力计算组合数，但是此时要满足a<p && b<p
int C(int a, int b){
    int res = 1;
    for (int i = a, j = 1; j <= b; i --, j ++){
        // 分子是 a*(a-1)*(a-2)*...*(a-b+1)    分母是1*2*3*...*b   分子分母都是b个数
        res = (ll)res * i % p * qmi(j, p - 2) % p;  // res = res * i / j
    }
    return res;
}

int lucas(ll a, ll b){
    if (a < p && b < p) return C(a, b);
    return (ll)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main(){
    cin >> n;
    while (n --){
        cin >> a >> b >> p;
        cout << lucas(a, b) << endl;
    }

    return 0;
}