求C(n, m)%p的值， n, m<=1e18， p = p1*p2*...pk. pi是质数。
先求出C(n, m)%pi的值， 然后这就是一个同余的式子。 用中国剩余定理求解。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define ll long long ll a[17], b[17]; void extend_Euclid(ll a, ll b, ll &x, ll &y) { if(b == 0) { x = 1; y = 0; return; } extend_Euclid(b, a % b, x, y); ll tmp = x; x = y; y = tmp - (a / b) * y; } ll mul(ll a, ll n, ll mod) { a = (a%mod+mod)%mod; n = (n%mod+mod)%mod; ll ret = 0; while(n) { if(n&1) ret = (ret+a)%mod; a = (a+a)%mod; n >>= 1; } return ret; } ll CRT(ll a[],ll m[],int n) { ll M = 1; ll ans = 0; for(int i=1; i<=n; i++) M *= m[i]; for(int i=1; i<=n; i++) { ll x, y; ll Mi = M / m[i]; extend_Euclid(Mi, m[i], x, y); ans = (ans + mul(mul(Mi, x, M), a[i], M))%M; } return (ans+M)%M; } ll pow(ll a, ll b, ll mod) { ll ret = 1; while(b) { if(b&1) ret = ret*a%mod; a = a*a%mod; b /= 2; } return ret; } ll C(ll n, ll m, ll mod) { ll a = 1, b = 1; for(int i = 1; i <= m; i++) { b = b*i%mod; a = a*(n-i+1)%mod; } return a*pow(b, mod-2, mod)%mod; } ll lucas(ll n, ll m, ll mod) { if(m == 0) return 1; return lucas(n/mod, m/mod, mod)*C(n%mod, m%mod, mod)%mod; } int main() { ll t, n, m, k; cin>>t; while(t--) { cin>>n>>m>>k; for(int i = 1; i <= k; i++) { scanf("%lld", &a[i]); } for(int i = 1; i <= k; i++) { b[i] = lucas(n, m, a[i]); } ll ans = CRT(b, a, k); cout<<ans<<endl; } return 0; }