一.  取模性质

　　加法 (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），问物几何？　　　　——《孙子算经》

推荐资料：

截取我看懂的部分：

　　从第二张图看出，只要求出Mi'的值就能按照最后一个公式计算出答案x，将Mi * Mi‘ = 1(mod mi)变形一下得到：

Mi * Mi' - n * mi = 1 其中Mi'和n未知分别设为x，y，另外两个已知设为分别设为a，b，再变形一下得到：ax + by = 1用扩展欧几里德算法求解x

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;}