與擴歐的聯系

在同余方程的求解過程中，我們通常需要將方程轉化為線性不定方程（Diophantine 方程）的形式，然后使用擴展歐幾里得算法（Extended Euclidean Algorithm, EEA）求解。

同余方程是怎么轉化為線性不定方程的？

Q：y 的符號變了，難道不會影響整個方程的解嗎？
A：
首先這個問題就搞混了同余方程究竟在干什么，同余方程求解的是x的解集，y只是一個中間變量，中間變量的系數只是為了滿足等式的合理性。

例題1

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

重點

$x$ 的通解公式為：$x=x_0+\frac{b}{d}?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;
}