Lucas+中国剩余定理 HDOJ 5446 Unknown Treasure-白红宇

Lucas+中国剩余定理 HDOJ 5446 Unknown Treasure

阅读量：6542 次

发布时间：2019-06-24

本文共 2216 字，大约阅读时间需要 7 分钟。

题意：很裸，就是求C (n, m) % (p1 * p2 * p3 * .... * pk)

分析：首先n，m<= 1e18, 要用到Lucas定理求，当然p[]的乘积<=1e18不能直接计算，但是pi<=1e5。接下来要知道中国剩余定理，所以先对每个pi计算出bi，注意在中国剩余定理的两数相乘会爆long long，所以用乘法取模，"但是这样的话exgcd返回值如果是负数就会出错，所以乘之前要取模成正的"，这句话不是很懂。

收获：老祖宗的智慧结晶一定要学

代码：

/************************************************* Author        :Running_Time* Created Time  :2015/9/15 星期二 13:40:41* File Name     :J.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;ll f[N]; void init(int p) { f[0] = 1; for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p;} ll pow_mod(ll a, ll x, ll p) { ll ret = 1; while (x) { if (x & 1) ret = ret * a % p; a = a * a % p; x >>= 1; } return ret;} ll Lucas(ll n, ll k, ll p) { //C (n, k) % p ll ret = 1; while (n && k) { ll nn = n % p, kk = k % p; if (nn < kk) return 0; ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p; n /= p, k /= p; } return ret;}ll multi_mod(ll a, ll b, ll p) { //a * b % p a = (a % p + p) % p; b = (b % p + p) % p; ll ret = 0; while (b) { if (b & 1) { ret += a; if (ret >= p) ret -= p; } b >>= 1; a <<= 1; if (a >= p) a -= p; } return ret;}ll ex_GCD(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll d = ex_GCD (b, a % b, y, x); y -= x * (a / b); return d;}ll China(int k, ll *b, ll *m) { ll M = 1, x, y, ret = 0; for (int i=1; i<=k; ++i) M *= m[i]; for (int i=1; i<=k; ++i) { ll w = M / m[i]; ex_GCD (w, m[i], x, y); ret += multi_mod (multi_mod (x, w, M), b[i], M); } return (ret + M) % M;}int main(void) { int T; scanf ("%d", &T); while (T--) { ll p[11], b[11]; ll n, m; int k; scanf ("%I64d%I64d%d", &n, &m, &k); for (int i=1; i<=k; ++i) { scanf ("%I64d", &p[i]); init (p[i]); b[i] = Lucas (n, m, p[i]); } printf ("%I64d\n", China (k, b, p)); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4810476.html

你可能感兴趣的文章