Mathematical knowledge: finding combinatorial number III - finding combinatorial number

subject ：AcWing 887. Find the combination number III
Given n Group inquiry , Each group is asked to give three integers a,b,p, among p Prime number , Please output C^b_amod p Value .

Input format
The first line contains integers n.

Next n That's ok , Each line contains a set of a,b,p.

Output format
common n That's ok , Each line outputs a solution to the query .

Data range
1≤n≤20,
1≤b≤a≤10¹⁸,
1≤p≤10⁵,

sample input ：

3
5 3 7
3 1 5
6 4 13

sample output ：

3
3
2

Topic analysis ：

From the above formula, we can know that the combinatorial number can be decomposed into smaller combinatorial numbers , We can use the fast power to find the inverse , To find the number of combinations

#include <iostream>

using namespace std;
typedef long long LL;

int p;

int qmi(int a,int k,int p) //  Find fast power 
{
    
    int res=1;
    while(k)
    {
    
        if(k&1)res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}
int C(int a,int b,int p) //  Find the combination number 
{
    
    if(b>a)return 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)%p;    
    }
    return res;
}
int lucas(LL a,LL b,int p) //  Lucas theorem 
{
    
    if(a<p&&b<p)return C(a,b,p);
    else return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main()
{
    
    int n;
    cin>>n;
    while(n--)
    {
    
        LL a,b;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }
    return 0;
}