与扩欧的联系

在同余方程的求解过程中，我们通常需要将方程转化为线性不定方程（Diophantine 方程）的形式，然后使用扩展欧几里得算法（Extended Euclidean Algorithm, EEA）求解。

同余方程是怎么转化为线性不定方程的？

Q：y 的符号变了，难道不会影响整个方程的解吗？
A：
首先这个问题就搞混了同余方程究竟在干什么，同余方程求解的是x的解集，y只是一个中间变量，中间变量的系数只是为了满足等式的合理性。

例题1

牛客网：【模板】同余方程

重点

$x$ 的通解公式为：$x=x_0+\frac{b}{d}\cdot k$
这意味着 $x$ 的解是以 $\frac{b}{d}$ 为周期的。

求最小正整数解对$x_0$模$\frac{b}{d}$就保证了它是最小整数，再使用模加模确保结果为正数即可x = (x % b + b) % b;

代码

#include<iostream>using namespace std;typedef long long LL;LL exgcd(LL a,LL b,LL& x,LL& y)
{if(b == 0){x = 1, y = 0;return a;}LL x1,y1;LL d = exgcd(b,a%b,x1,y1);x = y1, y = x1 - a/b*y1;return d;
}int main()
{int T; cin >> T;while(T--){LL a,b; cin >> a >> b;LL x,y;LL d = exgcd(a,b,x,y);if(d == 1){x = (x % b + b) % b;cout << x << endl;}else{cout << -1 << endl;}}return 0;
}

例题2

洛谷：P1516 青蛙的约会

分析

代码

#include<iostream>using namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL& x, LL& y)
{if(b == 0){x = 1, y = 0;return a;}LL x1,y1,d;d = exgcd(b, a%b, x1, y1);x = y1;y = x1 - a/b*y1;return d;
}int main()
{LL x,y,m,n,l;cin >> x >> y >> m >> n >> l;LL a = m - n, b = l, c = y - x;if(a < 0){a = -a, c = -c;}LL x0,y0;LL d = exgcd(a,b,x0,y0);if(c % d == 0){x0 = c / d * x0, y0 = c / d * y0;LL k1 = b / d;cout << (x0 % k1 + k1) % k1 << endl;}else{cout << "Impossible" << endl;}return 0;
}