hdoj 5446 Unknown Treasure 【lucas + CRT】

Unknown Treasure Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1820    Accepted Submission(s): 671
Problem Description
On the way to the next secret treasure hiding place, the mathematician discovered a cave unknown to the map. The mathematician entered the cave because it is there. Somewhere deep in the cave, she found a treasure chest with a combination lock and some numbers on it. After quite a research, the mathematician found out that the correct combination to the lock would be obtained by calculating how many ways are there to pick 
m  different apples among 
n  of them and modulo it with 
M . 
M  is the product of several different primes.
 
Input
On the first line there is an integer 
T(T≤20)  representing the number of test cases.
Each test case starts with three integers 
n,m,k(1≤m≤n≤1018,1≤k≤10)  on a line where 
k  is the number of primes. Following on the next line are 
k different primes 
p1,...,pk . It is guaranteed that 
M=p1⋅p2⋅⋅⋅pk≤1018  and 
pi≤105  for every 
i∈{1,...,k} .
 
Output
For each test case output the correct combination on a line.
 
Sample Input

       
       
       
       

        
        
        
        1
9 5 2
3 5
       
       
       
       

 
Sample Output

       
       
       
       

        
        
        
        6
       
       
       
       

 
标题:C(n,m)%(p[0]*p[1]*p[2]*...*p[k-1])を解く.ここでp[]は異なる質量数である.
考え方:p[0]*p[1]*...*p[k-1]が大きいので、lucasを直接使うことはできません.
質量数ごとに分けることを考える.
C(n, m) % p[0] = a[0], C(n, m) % p[1] = a[1]... C(n, m) % p[k-1] = a[k-1].
次の方程式のグループが得られます
A = a[0] (mod p[0])
A = a[1] (mod p[1])
...
A = a[k-1] (mod p[k-1]).
次はCRTで直接Aを求めればいいです.
問題は結果が正の整数であるとは言わなかったので,CRTが最後に0に解けると,そのまま戻る.ここでWAは3回やったo(′▽`)o
ACコード:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define debug printf("1
");
using namespace std;
struct ONE
{
    LL gcd(LL a, LL b){
        return b == 0 ? a : gcd(b, a%b);
    }
    LL lcm(LL a, LL b){
        return a / gcd(a, b) * b;
    }
    void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
    {
        if(b == 0) {d = a, x = 1, y = 0;}
        else
        {
            exgcd(b, a%b, d, y, x);
            y -= x * (a / b);
        }
    }
    LL CRT(LL l, LL r, LL *a, LL *m)
    {
        LL LCM = 1;
        for(LL i = l; i <= r; i++)
            LCM = LCM / gcd(LCM, m[i]) * m[i];
        for(LL i = l+1; i <= r; i++)
        {
            LL d, x, y, A = m[l], B = m[i], c = a[i] - a[l];
            exgcd(A, B, d, x, y);
            if(c % d) return -1;
            LL mod = m[i] / d;
            LL k = ((x / d * c) % mod + mod) % mod;
            a[l] = m[l] * k + a[l];
            m[l] = m[l] / d * m[i];
        }
        //if(a[l] == 0)       
          //  return LCM;
        return a[l];
    }
};
ONE crt;
LL fac[100000+10];
void getfac(LL p)
{
    fac[0] = 1 % p;
    for(LL i = 1; i <= p; i++)
        fac[i] = fac[i-1] * i % p;
}
struct TWO
{
    LL pow_mod(LL a, LL n, LL p)
    {
        LL ans = 1 % p;
        while(n)
        {
            if(n & 1)
                ans = ans * a % p;
            a = a * a % p;
            n >>= 1;
        }
        return ans;
    }
    LL C(LL n, LL m, LL p)
    {
        if(n < m)
            return 0;
        else
            return fac[n] * pow_mod(fac[m]*fac[n-m]%p, p-2, p) % p;
    }
    LL Lucas(LL n, LL m, LL p)
    {
        if(m == 0)
            return 1 % p;
        else
            return C(n%p, m%p, p) * Lucas(n/p, m/p, p) % p;
    }
};
TWO LUCAS;
LL p[15], a[15], m[15];
int main()
{
    LL t;
    scanf("%d", &t);
    while(t--)
    {
        LL N, M, k;
        scanf("%lld%lld%lld", &N, &M, &k);
        for(LL i = 0; i < k; i++)
        {
            scanf("%lld", &p[i]);
            m[i] = p[i];
            getfac(p[i]);
            a[i] = LUCAS.Lucas(N, M, p[i]);
        }
        printf("%lld
", crt.CRT(0, k-1, a, p));
    }
    return 0;
}