[C++][算法基础]求组合数(III)

给定 𝑛 组询问，每组询问给定三个整数 𝑎,𝑏,𝑝，其中 𝑝 是质数，请你输出  的值。

输入格式

第一行包含整数 𝑛。

接下来 𝑛 行，每行包含一组 𝑎,𝑏,𝑝。

输出格式

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

数据范围

1≤n≤20,
1≤b≤a≤,
1≤p≤,

输入样例：

3
5 3 7
3 1 5
6 4 13

输出样例：

3
3
2

代码：

#include
using namespace std;
 
int n,p;
long long a,b;
 
long long QuickMOD(int a,int b,int p){
    long long res = 1;
    while(b != 0){
        if((b & 1) == 1){
            res = (long long) res * a % p;
        }
        a = (long long) a * a % p;
        b /= 2;
    }
    return res;
}
 
long long C(long long a,long long b,int p){
    long long res = 1;
    for(int i = 1,j = a;i <= b;i ++,j --){
        res = (long long)res * j % p;
        res = (long long)res * QuickMOD(i,p-2,p) % p;
    }
    return res;
}
 
long long Lucas(long long a,long long b,int p){
    if(a < p && b < p){
        return C(a,b,p);
    }else{
        return (long long) Lucas(a%p,b%p,p) * Lucas(a/p,b/p,p) % p;
    }
}
 
int main(){
    cin>>n;
    while(n--){
        cin>>a>>b>>p;
        cout<<Lucas(a,b,p)<
    }
    return 0;
}