线性同余方程与中国剩余定理
线性同余方程
问题形式： 给定 a、b、m，求整数 x 使得 a·x ≡ b (mod m)。它等价于存在整数 y 满足 a·x - m·y = b，即一个二元一次不定方程。
有解条件： 由裴蜀定理（Bézout），ax + my 能取到的值恰好是 gcd(a, m) 的所有倍数，所以方程有解 当且仅当 b 是 gcd(a, m) 的倍数。
求解步骤：
- 用扩展欧几里得求出 ax’ + my’ = gcd(a, m) 的一组特解 x’；
- 把特解放大 b / g 倍，得到原方程的一个特解 x0 = x’ · (b / g)；
- 通解为 x = x0 + k · (m / g)（k 为任意整数），因此把 x0 对 m/g 取模（取正）即可得到最小非负解。
例题
题意
给定 组数据 ，对于每组数求出一个 ，使其满足 若无解，则输出
impossible。输入格式
第一行一个整数 。
接下来 行，每行三个整数 。输出格式
共 行，每行输出一个满足条件的 （若存在）；若无解则输出
impossible。数据范围
import java.io.*;import java.util.StringTokenizer;
public class Main { /* 扩展欧几里得：求 ax + by = gcd(a,b)，返回 gcd */ static long exgcd(long a, long b, long[] xy) { if (b == 0) { xy[0] = 1; xy[1] = 0; return a; } long g = exgcd(b, a % b, xy); long x = xy[0], y = xy[1]; xy[0] = y; xy[1] = x - (a / b) * y; return g; }
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine().trim()); while (n-- > 0) { StringTokenizer st = new StringTokenizer(br.readLine()); long a = Long.parseLong(st.nextToken()); long b = Long.parseLong(st.nextToken()); long m = Long.parseLong(st.nextToken());
long[] xy = new long[2]; long g = exgcd(a, m, xy); // a*x' + m*y' = g if (b % g != 0) { // 裴蜀定理：b 必须是 g 的倍数才有解 pw.println("impossible"); } else { long x = xy[0] * (b / g) % m; // 放大 b/g 倍得到特解 x = (x % m + m) % m; // 取最小非负解 pw.println(x); } } pw.flush(); }}中国剩余定理
解决的问题： 求解同余方程组
x ≡ m₁ (mod a₁)，x ≡ m₂ (mod a₂)，…，x ≡ mₙ (mod aₙ)
其中各模数 aᵢ 不一定互质（互质时用经典的 CRT 公式；不互质时用下面的”两两合并法”，它是通法）。
两两合并法： 假设已经合并出前 k 个方程的解：x ≡ m₁ (mod a₁)，即 x = a₁·t + m₁。代入下一个方程 x ≡ m₂ (mod a₂)，得到 a₁·t ≡ m₂ - m₁ (mod a₂)——这就是一个线性同余方程。用扩展欧几里得解出 t（若 m₂ - m₁ 不是 gcd(a₁, a₂) 的倍数则整个方程组无解），回代得到新的 m₁’ = a₁·t + m₁，新的模数 a₁’ = lcm(a₁, a₂) = a₁/g·a₂。重复 n-1 次即可。最终答案就是最后留下的 m₁（取最小非负）。
表达整数的奇怪方式
题目描述
给定 个整数 和 ，求一个最小非负整数 ，满足
若不存在这样的 ，输出 。输入格式
第 行：整数 。
第 到 行：每行两个整数 ，用空格隔开。输出格式
输出最小非负整数 ；若不存在，输出 。
数据范围
import java.io.*;import java.util.StringTokenizer;
public class Main { /* 扩展欧几里得：ax + by = gcd(a,b)，返回 gcd */ static long exgcd(long a, long b, long[] xy) { if (b == 0) { xy[0] = 1; xy[1] = 0; return a; } long g = exgcd(b, a % b, xy); long x = xy[0], y = xy[1]; xy[0] = y; xy[1] = x - (a / b) * y; return g; }
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); boolean ok = true;
// 读入第一个方程 x ≡ m1 (mod a1) StringTokenizer st = new StringTokenizer(br.readLine()); long a1 = Long.parseLong(st.nextToken()); long m1 = Long.parseLong(st.nextToken());
// 依次把后面的方程合并进来 for (int i = 1; i < n; i++) { st = new StringTokenizer(br.readLine()); long a2 = Long.parseLong(st.nextToken()); long m2 = Long.parseLong(st.nextToken());
// 解 a1 * t ≡ m2 - m1 (mod a2) long[] xy = new long[2]; long g = exgcd(a1, a2, xy); if ((m2 - m1) % g != 0) { ok = false; break; } // 无解
long k1 = xy[0] * ((m2 - m1) / g); // 特解 long mod = a2 / g; k1 = (k1 % mod + mod) % mod; // t 的最小非负解
m1 = m1 + a1 * k1; // 合并后的余数 a1 = a1 / g * a2; // 合并后的模数 = lcm(a1, a2) m1 = (m1 % a1 + a1) % a1; // 取最小非负 } System.out.println(ok ? m1 : -1); }}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时