887. 求组合数 III

题目链接https://www.acwing.com/problem/content/889/
题目：

思路：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
int n;
int qmi(LL a,int k,int p){int res=1;while(k){if(k&1)res=(LL)res*a%p;k>>=1;a=(LL)a*a%p;}return res;
}
int cc(LL a,LL b,int p){if(a<b) return 0;int res=1;int i=1,j=a;for(;i<=b;j--,i++){res=(LL)res*j%p;res=(LL)res*qmi(i,p-2,p)%p;}return res;
}
int lucas(LL a,LL b,int p){if(a<p&&b<p)return cc(a,b,p);return (LL)cc(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main(){LL a,b;int p;cin>>n;while(n--){cin>>a>>b>>p;printf("%d\n",lucas(a,b,p));}return 0;
}

求组合数的方法总结https://blog.csdn.net/weixin_46028214/article/details/115920131