FZU - 2020 -组合【扩展欧几里得+逆元+Lacus】

给出组合数C(n,m), 表示从n个元素中选出m个元素的方案数。例如C(5,2) = 10, C(4,2) = 6.可是当n,m比较大的时候，C(n,m)很大！于是xiaobo希望你输出 C(n,m) mod p的值！
Input
输入数据第一行是一个正整数T,表示数据组数 (T <= 100) 接下来是T组数据，每组数据有3个正整数 n, m, p (1 <= m <= n <= 10^9, m <= 10^4, m < p < 10^9, p是素数)
Output
对于每组数据，输出一个正整数，表示C(n,m) mod p的结果。
Sample Input
2
5 2 3
5 2 61
Sample Output
1
10

#include<iostream>
#include<cstdio>

using namespace std;

#define ll long long

ll exgcd(int a,int b,int&x,int&y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int ans=exgcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}

ll cal(int a,int m)
{
    int x,y;
    int gcd=exgcd(a,m,x,y);
    if(1%gcd!=0) return -1;
    x*=1/gcd;
    m=abs(m);
    int ans=x%m;
    if(ans<=0)
        ans+=m;
    return ans;
}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n,m,p,ans1=1,ans2=1;
        cin>>n>>m>>p;
        for(ll i=n-m+1; i<=n; i++)
        {
            ans1=ans1*i;
            ans1=ans1%p;
        }
        for(ll i=2; i<=m; i++)
        {
            ans2=ans2*i;
            ans2=ans2%p;
        }
        printf("%lld\n",ans1*cal(ans2,p)%p);
    }
}