Lucas用来求C(n,m)%p的值，适用于解决n,m较大，p(一定为素数)小于1e6的情况。
#include <iostream> #include <cstdio> #include <cstring> #define ll long long using namespace std; const int maxn = 1e6+5; const int mod = 1e9+7; using namespace std; ll quick_mod(ll a, ll b, ll c) { ll ans = 1; while(b) { if(b & 1) ans = (ans*a)%c; b>>=1; a = (a*a)%c; } return ans; } ll fac[maxn]; void Get_Fac(ll m)///m! { fac[0] = 1; for(int i=1; i<=m; i++) fac[i] = (fac[i-1]*i) % m; } ll Lucas(ll n, ll m, ll p) { ll ans = 1; while(n && m) { ll a = n % p; ll b = m % p; if(a < b) return 0; ans = ( (ans*fac[a]%p) * (quick_mod(fac[b]*fac[a-b]%p,p-2,p)) ) % p; n /= p; m /= p; } return ans; } int main() { ll n, m, p; cin>>n>>m>>p; Get_Fac(p); cout<<Lucas(n, m, p)<<endl; //C(n,m)%p return 0; }