餘數專題

一.  取模性質

　　加法 (a + b) % p = a % p + b % p;

　　減法 (a - b)  % p = a % p  - b % p;

　　乘法 (a * b)  % p = a % p * b % p;

　　但是除法。。。。。。

　　假設：a * b % p = c， 已知 b, c, p 求 a

　　那麼，a = c * d % p，c就是b的逆元，即1 / b

經常用到的乘方取模和乘法取模。(找不到合适的地方，放這裡算了)

int pow_mod(int x, int n, int p)    {       //x ^ n % p
    int ret = 1;
    while (n)   {
        if (n & 1)  {
            ret = 1ll * ret * x % p;
        }
        x = 1ll * x * x % p;
        n >>= 1;
    }
    return ret;
}

int multi_mod(int a, int b, int p)  {       //a * b % p
    int ret = 0;
    a = (a % p + p) % p;
    b = (b % p + p) % p;
    while (b)   {
        if (b & 1)  {
            ret += a;
            if (ret >= p)   ret -= p;
        }
        b >>= 1;
        a <<= 1;
        if (a >= p) a -= p;
    }
    return ret;
}
      

二. 逆元求法

　　記1 / b 為 inv (b)

　　求法1：

　　　　結論：　　

　　　   證明：　

　　　　　　　　　

void Inv(int n, int p)    {
    inv[1] = 1;
    for (int i=2; i<=n; ++i)    {
        inv[i] = 1ll * (p - p / i) * inv[p%i] % p;
    }
}      

　　

　　求法2：

int Inv(int a)   {
    return pow_mod (a, MOD - 2, MOD);
}
      

　　求法3：

int Inv(int a, int p)  {
    int x, y;
    int d = ex_GCD (a, p, x, y);
    if (d == 1) return (x % p + p) % p;
    else	return -1;
}
      

 三. 中國剩餘定理

　　今有物不知其數，三三數之剩二（除以3餘2），五五數之剩三（除以5餘3），七七數之剩二（除以7餘2），問物幾何？　　　　——《孫子算經》

推薦資料：POJ1006: 中國剩餘定理的完美演繹　　中國剩餘定理(百度文庫)

截取我看懂的部分：

int China(int k, int *b, int *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);　　　　　　//防止爆long long，用乘法取模
    }
    return (ret + M) % M;
}
 
int main(void)    {
    m[1] = 3;   m[2] = 5;   m[3] = 7;
    b[1] = 2;   b[2] = 3;   b[3] = 2;
    printf ("%d\n", China (3, b, m));
 
    return 0;
}
      

編譯人生，運作世界！