题目描述

Q*:1.求阶乘的时候为什么没有 求(a - b)! ?
* A:循环最后的终止条件是 i < b ，终止的时候算出的是 (B!)^-1和(A - B!) 相乘就是 Ca,b
* Q:2.可以根据这个把前一道题改进？
* A:会超时，上一题可以开1e5的数组，这道题数据不能开。
* Q:3.费马定理要求互质，如果b变成了p的倍数，就没有逆元了把？
* A:每一次再计算吗qmi之前，lucas定理限定了b >= p，如果p是质数，一定与b互质。
易错点：
1.qmi函数内部不是if 是 while

样例

算法1

$O(p* log p * logp N)

#include<iostream>
using namespace std;
typedef long long LL;
int p;
/*如果要防止溢出，但是返回值是int类型的话，解决方法：进行乘法运算的时候强转成LL，再由高精度转低精度。*/
int qmi(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1)res = (LL)a * res % p;
        b >>= 1;
        a = (LL) a * a %p;
    }
    //cout << res << endl;
    return res;
}

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