生成卢卡斯定理的 c++代码

以下是一个生成卢卡斯定理的C++代码示例：

#include <iostream>

// 计算 a^b mod m 的结果
long long int power(long long int a, long long int b, long long int m) {
    long long int result = 1;
    a = a % m;
    
    while (b > 0) {
        if (b % 2 == 1)
            result = (result * a) % m;
        
        a = (a * a) % m;
        b /= 2;
    }
    
    return result;
}

// 计算组合数 C(n, k) mod p 的结果
long long int lucas_theorem(long long int n, long long int k, long long int p) {
    if (k == 0)
        return 1;
    
    long long int ni = n % p;
    long long int ki = k % p;
    
    if (ni < ki)
        return 0;
    
    long long int numerator = 1;
    long long int denominator = 1;
    
    for (int i = 0; i < ki; i++) {
        numerator = (numerator * (ni - i)) % p;
        denominator = (denominator * (i + 1)) % p;
    }
    
    // 使用扩展欧几里得算法求逆元素
    long long int inverse_denominator = power(denominator, p - 2, p);
    
    return (numerator * inverse_denominator) % p;
}

int main() {
    long long int n = 10;
    long long int k = 3;
    long long int p = 13;
    
    long long int result = lucas_theorem(n, k, p);
    std::cout << "Lucas定理结果: " << result << std::endl;
    
    return 0;
}

这段代码中的`lucas_theorem`函数用于计算卢卡斯定理。在该函数中，我们首先对输入的`n`和`k`进行取模操作，然后使用循环计算分子和分母的乘积，并使用扩展欧几里得算法求解乘法逆元，最后返回结果。

在这个例子中，我们计算了C(10, 3) mod 13的结果。你可以根据需要修改输入的`n`、`k`和`p`值来进行不同的计算。