大整数取模,lucas 定理
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define LL __int64 LL n,m,p; LL Quick_Mod(LL a,LL b,LL mod){ LL r = 1; while(b){ if(b & 1) r = (r * a) % mod; a = (a * a) % mod; b >>= 1; } return r; } LL Cm(LL n,LL m,LL p){ LL a,b,r = 1; for(LL i = 1;i <= m;i++){ a = (n + i - m) % p; b = i % p; r = r *(a * Quick_Mod(b,p - 2,p) % p) % p; } return r; } LL Lucas(LL n,LL m,LL p){ if(m == 0) return 1; return (Lucas(n/p,m/p,p) * Cm(n % p,m % p,p)) % p; } int main(){ int T; while(~scanf("%d",&T)){ while(T--){ scanf("%I64d%I64d%I64d",&n,&m,&p); printf("%I64d\n",Lucas(n,m,p)); } } return 0; }