裴属定理

若 a，b 是整数，且 gcd(a, b) = d，那么对于任意的 x，y，a * x + b * y 一定是 d 的倍数，特别地，一定存在整数 x，y 使得 a * x + b* y = d。

扩展欧几里得算法

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{if (!b){x = 1; y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= (a/b) * x;return d;
}

线性同余方程

因为 a∗x ≡ b(mod m) 等价于 a∗x−b 是 m 的倍数，因此线性同余方程等价为a∗x+m∗y = b
根据裴蜀定理，上述等式有解当且仅当 gcd(a,m) | b
因此先用扩展欧几里得算法求出一组整数 $x_0$，y_0, 使得 a∗$x_0$+m∗$y_0$ = gcd(a, m)。 然后 x = $x_0$∗b / gcd(a, m) % m 即是所求。

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;int exgcd(int a, int b, int &x, int &y)
{if (!b){x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main()
{int n;scanf("%d", &n);while (n -- ){int a, b, m;scanf("%d%d%d", &a, &b, &m);int x, y;int d = exgcd(a, m, x, y);if (b % d) puts("impossible");else printf("%d\n", (LL)b / d * x % m);}return 0;
}