模運算——大整數取模、幂取模等

一、加法、減法、乘法取模

int add_mod(int a, int b, int p)
{
    a %= p; b %= p;
    return (a + b) % p;
}

int sub_mod(int a, int b, int p)
{
    a %= p; b %= p;
    return (a - b + p) % p;                //a mod n可能小于b mod n，需要在結果加上n
}

LL mul_mod(LL a, LL b, LL p)
{
    a %= p; b %= p;
    return a * b % p;    //a mod n和b mod n的乘積可能超LL
}      

二、大整數取模

求n mod m 的值，(n ≤10100,m ≤109)

思路：首先，将大整數根據秦九韶公式寫成“自左向右”的形式：4351 = ((4 * 10 + 3) * 10 + 5) * 10 + 1,然後利用模的性質，逐漸取模。

1 const int maxn = 100 + 10;
 2 char n[maxn];
 3 int m;
 4 
 5 int biginteger_mod(char* n, int m)
 6 {
 7     int len = strlen(n);
 8     int ans = 0;
 9     for(int i = 0;i < len;i++)
10         ans = (int)(((long long)ans * 10 + n[i] - '0') % m);
11     return ans;
12 }      

三、幂取模

1 LL pow_mod(LL a, LL n, LL m)
2 {
3     if (n == 0)  return 1;
4     LL ans = pow_mod(a, n / 2, m);
5     ans = ans * ans % m;
6     if (n % 2)  ans = ans * a % m;
7     return ans;
8 }      

個性簽名：時間會解決一切