887 求组合数 III（组合计数--卢卡斯定理，定义求解）

887 求组合数 III（组合计数--卢卡斯定理，定义求解）

1. 问题描述：

给定 n 组询问，每组询问给定三个整数 a，b，p，其中 p 是质数，请你输出 Cba mod p 的值。

输入格式

第一行包含整数 n。接下来 n 行，每行包含一组 a，b，p。

输出格式

共 n 行，每行输出一个询问的解。

数据范围

1 ≤ n ≤ 20，
1 ≤ b ≤ a ≤ 10 ^ 18，
1 ≤ p ≤ 10 ^ 5,

输入样例：

3
5 3 7
3 1 5
6 4 13

输出样例：

3
3
2
来源：https://www.acwing.com/problem/content/description/889/

2. 思路分析：

这道题目由于a，b可能非常大，而p相对比较小（由于a可能非常大，所以a可能是p的倍数，a关于p的逆元可能不存在，所以不能够使用费马小定理来求解）此时就需要使用卢卡斯定理来求解对应的组合数，需要使用到下面这个公式进行求解，感觉卢卡斯定理的证明过程还是比较复杂的，时间复杂度为O(plognp)

3. 代码如下：

python（超时）：

class Solution:
    # 快速幂
    def quickPower(self, a: int, b: int, p: int):
        res = 1
        while b > 0:
            if b & 1:
                res = res * a % p
            a = a * a % p
            b >>= 1
        return res

    # 使用公式求解对应的组合数(阶乘的形式)
    def C(self, a: int, b: int, p: int):
        if a < b: return 0
        up = down = 1
        i, j = a, 1
        while j <= b:
            up *= i
            down *= j
            i -= 1
            j += 1
        # 由费马小定理可知a ^ (p - 2)就是a关于p的逆元
        return up * self.quickPower(down, p - 2, p) % p

    # p为取模数
    def Lucas(self, a: int, b: int, p: int):
        if a < p and b < p: return self.C(a, b, p)
        return self.C(a % p, b % p, p) * self.Lucas(a // p, b // p, p) % p

    # 卢卡斯定理求解
    def process(self):
        n = int(input())
        for i in range(n):
            a, b, p = map(int, input().split())
            print(self.Lucas(a, b, p))


if __name__ == "__main__":
    Solution().process()

c++：

#include 
using namespace std;
typedef long long LL;

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

LL C(LL a, LL b, LL p){
    LL res = 1;
    for(int i = 1, j = a; i <= b;++i, --j){
        res = res * j % p;
        res = res * quickPower(i, p - 2, p) % p;
    }
    return res % p;
}

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

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