a mod b 表示 a 除以 b 的余数，在高级语言中表示成 a % b 。 int mod(int a,int b) { return a%b; }

我们先记住下面几个公式：

• 1. (a+b) mod n=((a mod n)+(b mod n)) mod n

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

• 2.(a−b) mod n=((a mod n)−(b mod n)+n) mod n
  注意这里的 a mod n 可能会小于 b mod n，则需要在结果上加上 n 。

int minus_mod(int a, int b, int n) { a %= n; b %= n; return (int) ((long long)(a - b + n) % n); }

• 3.ab mod n=(a mod n)(b mod n) mod n
  注意这里的 a mod n 和 b mod n 的乘积可能会溢出

int mul_mod(int a, int b, int n) { a %= n; b %= n; return (int) ((long long)a * b % n); }

---

大整数取模：

计算一下222222222222222222222222 mod 1234的结果，是否可以用下面的程序计算？ int mod(long long a, long long b) { return a%b; } 它计算出来的结果是 441，可惜正确答案是1036
显然，我们能发现其中的错误在哪，因为long long的范围是9223372036854775807，所以一旦 a 大于long long的范围，那就肯定是错的。所以我们不能用整型来保存整数，要用字符数组来保存。

分析：

首先将大整数写成”自左向右“的形式，比如1234=((1∗10+2)∗10+3)∗10+4，然后再用上面的公式1进行每步取模。
代码如下： #include #include using namespace std; int main() { char n[100]; int m; scanf("%s%d",n,&m); int len = strlen(n); int ans = 0; for(int i=0; iint)(((long long)ans*10 + n[i] - '0') % m); } printf("%d ",ans); return 0; } 这样再大的整数都没有问题。

---

幂取模：

如何计算出 abmodn 的值
我们可以使用上面的公式3，进行每步取模，因为ab=a∗a∗a∗a∗a∗a∗...∗a共有b个a相乘，每一次 ans = ans * a%n 即可。 int pow_mod(int a, int b, int n) { int ans = 1; for(int i=0; iint)((long long)ans * a % n); } return ans; } 这里的时间复杂度就是O(n)了，但是如果b很大呢，所以我们需要优化一下： 这里采用二分法的思想。
比如 a14=(