题目链接：
题目描述：
就是有n个苹果，要选出来m个，问有多少种选法？还有k个素数，p1,p2,p3,...pk，结果对lcm(p1,p2,p3.....,pk)取余。
解题思路：
Lucas + 中国剩余定理，注意的是中国剩余定理的时候有可能会爆long long。然后用一个快速加法就好辣。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef __int64 LL;
const int maxn = ; LL quick_mul (LL a, LL b, LL mod)
{
LL res = ;
while (b)
{
if (b % )
res = (res * a) % mod;
a = (a * a) % mod;
b /= ;
}
return res;
} LL quick_add (LL a, LL b, LL mod)
{
LL res = ;
while (b)
{
if (b % )
res =(res + a) % mod;
a = (a + a) % mod;
b /= ;
}
return res;
} LL C (LL n, LL m, LL mod)
{
if (n < m)
return ;
LL ans = ;
for (int i=; i<=m; i++)
{
LL a = (n - m + i) % mod;
LL b = i % mod;
ans = ans * (a * quick_mul(b, mod - , mod) % mod) % mod;
}
return ans;
} LL Extended_Euclid (LL a, LL b, LL &x, LL &y)
{//a, b只能是正数
if (b == )
{
x = ;
y = ;
return a;
} LL r = Extended_Euclid (b, a%b, x, y), t;
t = x;
x = y;
y = t - a / b * y;
return r;
} LL CRT (LL a[], LL b[], LL n)
{
LL M = , ans = ;
LL Mi, x, y; for (int i=; i<n; i++)
M *= a[i]; for (int i=; i<n; i++)
{
Mi = M / a[i];
LL d = Extended_Euclid (Mi, a[i], x, y);
x = (x % a[i] + a[i]) % a[i];
//注意，这里的x有可能是负数要注意取mod，变成正的 //或者quick_add 的第二个参数传Mi
LL res = quick_add (x, Mi, M);
res = quick_add (res, b[i], M);
ans = (ans + res) % M;
}
return (ans + M) % M;
}
LL Lucas (LL n, LL m, LL mod)
{
if (m == )
return ;
return (C(n%mod, m%mod, mod) * Lucas(n/mod, m/mod, mod)%mod);
} int main ()
{
LL t, n, m, k, a[maxn], b[maxn];
scanf ("%I64d", &t);
while (t --)
{
scanf ("%I64d %I64d %I64d", &n, &m, &k);
for (int i=; i<k; i++)
{
scanf ("%I64d", &a[i]);
b[i] = Lucas (n, m, a[i]);
}
printf ("%I64d\n", CRT (a, b, k));
}
return ;
}