分析

• 上两题中的方法这里都不能使用，因为b、a范围太大了。本题需要使用到卢卡斯定理(lucas)。

• 卢卡斯定理：

$$ C_a^b = C_{a \ (mod \ p)} ^ {b \ (mod \ p)} \times C_{a / p} ^ {b / p} \ \ (mod \ p) $$

递归求解即可。

• 关于$C_{a \ (mod \ p)} ^ {b \ (mod \ p)}$的求解，直接使用定义求解即可：

$$ C_a^b = \frac{a \times (a-1) \times … \times (a-b+1)}{1 \times 2 \times … \times b} $$

• 设$N=10^{18}$，求解$C_{a \ (mod \ p)} ^ {b \ (mod \ p)}$的复杂度为$O(p \times log(p))$的（因为要求解 $2^{p-2}\ \%p$ 的值，然后预处理所有的阶乘以及逆元的阶乘），后面的 $C_{a / p} ^ {b / p}$ 可以递归求解，可以看成p进制的数据，因此需要递归$log_p(N)$次，因此总时间复杂度为：$log_p(N) \times p \times log(p)$。一般来说p值比较大，因此$log_p(N)$比较小，可以忽略，时间复杂度是$O(p \times log(p))$的，和上一题的时间复杂度差不多。

• 关于卢卡斯定理的证明，不要求掌握。

#include <iostream>

using namespace std;

typedef long long LL;

int p;

// 计算 a^b % p
int qmi(int a, int b) {

    int res = 1 % p;
    while (b) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

// 根据定义计算C(a, b) % p
int C(int a, int b) {

    if (b > a) return 0;  // 不合法情况，直接返回0

    int res = 1;
    for (int i = 1, j = a; i <= b; i++, j--) {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2) % p;
    }
    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() {

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

    return 0;
}