重铸华农荣光 我辈义不容辞

Day 21(twenty-first)-lucas

这板子是要背一下的，背一下也没什么不好的，任何学科的学习都是建立在记忆上的，是这样的

#include<iostream>
using namespace std;

typedef long long ll;

int qmi(int a,int k,int p)
{
    int ans=1;
    while(k)
    {
        if(k&1) ans=(ll)ans*a%p;
        k>>=1;
        a=(ll)a*a%p;
    }
    return ans;
}

int C(int a,int b,int p)
{
    if(b>a) return 0;
    int ans=1;
    for(int i=1,j=a;i<=b;j--,i++)
    {
        ans=(ll)ans*j%p;
        ans=(ll)ans*qmi(i,p-2,p)%p;
    }
    return ans;
}

int lucas(ll a,ll b,int p)
{
    if(a<p&&b<p) return C(a,b,p);
    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;
        int p;
        cin>>a>>b>>p;
        cout<<lucas(a,b,p)<<endl;
    }

    return 0;
}