1.大整数取模

（1）题意：输入正整数n,m，输出n mod m的值。n≤10^100,m≤10^9。 （2）思路：把大整数拆开，逐步取模。 #define N 1000+10 char n[N]; int m; int main() { scanf("%s%d", n, &m); int len = strlen(n); int ans = 0; for (int i = 0; i < len; i++) ans = (int)(((long long)ans * 10 + n[i] - '0') % m); printf("%d ", ans); }

2.幂取模

（1）题意：输入正整数a,n,m，输出 a^n mod m 的值。a,n,m≤10^9。 （2）思路：利用分治法解决。 int pow_mod(int a, int n, int m) { if (n == 0)return 1; int x = pow_mod(a, n / 2, m); long long ans = (long long)x*x%m; if (n & 1)ans = ans*a%m; return (int)ans; } 大多数时候用如下代码更简洁 typedef long long LL; LL pow_mod(LL x, LL n, LL mod) { LL ans = 1; while (n > 0) { if (n & 1)ans = ans*x%mod;//如果二进制最低位是1，那么乘以x^(2^i) x = x*x%mod;//将x平方 n >>= 1; } return ans; }

3.模线性方程组 （1）题意：输入正整数a,b,n,解方程 ax ≡ b (mod n) 。a,b,n≤10^9。 （2）思路：等价于求解 ax-ny=b。先求出g=gcd(a,n)，解方程 ax-ny=g得到一组解x0,y0。那么原方程解为x0*(b/g),y0*(b/g)。 void exgcd(int a, int b, int&d, int&x, int&y) { if (!b){ d = a, x = 1, y = 0; } else { exgcd(b, a%b, d, y, x); y -= x*(a / b); } } int main() { int a, b, n; cin >> a >> b >> n; int g, x, y; exgcd(a, n, g, x, y); x *= (b / g); printf("%d ", x); }