扩展欧几里得
内容
梗概
对于任意两个数$a, b$，两者间必有最大公因子$g$,使得$a = k_1g,b = k_2g$ ;
可得必有整数$x, y$ 使$ax + by = gcd(a,b)$
板子
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
bool find_any_solution(ll a, ll b, ll c, ll &x0, ll &y0, ll &g)
{
g = ex_gcd(abs(a), abs(b), x0, y0);
if (c % g)
return false;
x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;
}丢番图求解
丢番图求一个解
//有解返回true，无解返回false
bool find_one_solution(ll a, ll b, ll &x, ll &y, ll C) {
ll d = exgcd(abs(a), abs(b), x, y);
if(C % d) return false;
x *= C / d;
y *= C / d;
if(a < 0) x = -x;
if(b < 0) y = -y;
return true;
}扩展欧几里得基本应用
https://ac.nowcoder.com/acm/contest/21289/A
题目描述：
求关于 $x$ 的同余方程$ax≡1(mod\ b)$的最小正整数解，若无解，输出”-1”。
对题目的方程进行变化，可以得到 $a x + b y = 1$ ，故而对其求 $x$ 的最小正整数解即可(中间计算时可能会爆 int , 故最好用 long long存储 )
#include <iostream>
using namespace std;
using ll = long long;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve() {
ll a, b;
cin >> a >> b;
ll x, y;
ll d = exgcd(a, b, x, y);
//此处因为C是1，所以如果b不为1就无解
if(d != 1) {
puts("-1");
return;
}
//因为d是1，所以b/d = b
x = (x % b + b) % b;
cout << x << endl;
}
int main() {
int T;
cin >> T;
while(T --)
solve();
return 0;
}
中国剩余定理（线性同余方程）
线性同余方程求解是扩展欧几里得的求解应用之一，大意是需要求一个 $x$ , $x$ 满足以下条件 $x$ ≡ $m_i$ $(mod\ a_i)$ 形式大体如下
$$
x= \left{ \begin{aligned} m_1\ (mod\ a_1) \ m_2\ (mod\ a_2) \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m_n\ (mod\ a_n) \end{aligned} \right.
$$
对于以上公式，可以进行变形得：
$$
x=\left{ \begin{aligned} m_1 + k_1a_1\ (1) \ m_2+k_2a_2\ (2) \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ m_n + k_na_n\ (n) \end{aligned} \right.
$$
由 $(1)\ (2)$ 可推导得出 ：
$$
m_1 + k_1a_1 = m_2 + k_2a_2
=> k_1a_1 - k_2a_2 = m_2 - m_1
$$
通过扩展欧几里得可以求出以上丢番图的一个解 $x_0\ y_0$ $(d = exgcd(a1, a2, x0, y0))$
若 $d$ 不能被 $m2 - m1$ 整除，则证明无解（扩展欧几里得里的解释），否则有
有 $k_1 = x_0 + k \times \lfloor \frac{a2}{d} \rfloor $
之后再将 $k_1$ 带入 $(1)$ 可得 ：
$x = m_1 + k_1a_1$
$x = m_1 + (x_0 + k \times \lfloor \frac{a_2}{d} \rfloor) \times a_1$
$x = m_1 + x_0 \times a_1 + k \times \lfloor \frac{a_1a_2}{d} \rfloor $
故可得一个新的关系式：
$x = m_0 + k \times a_0$
其中：$m_0=m_1 + x_0 \times a_1$ ; $ a_0 = \lfloor \frac{a_1a_2}{d} \rfloor $
又因为$d$ 是$a_1a_2$ 的最大公约数，所以 $\lfloor \frac{a_1a_2}{d} \rfloor$ 是$a_1 a_2$ 的最小公倍数，综上，可以不断对线性方程组进行合并，得到最后的答案 $x = m\ (mod\ a)$
中国剩余定理基本应用
求线性方程组的解：（链接）https://ac.nowcoder.com/acm/contest/21289/D
解线性同余方程组的板子题，注意计算中间值时可能会溢出 $long\ long$ 适当用 $ {__int 128_t} $ 作为中间值
#include <iostream>
using namespace std;
using u128 = __int128_t;
using ll = long long;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = 1;
y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
int n;
cin >> n;
//将第一对a1,m1记录
ll a1, m1;
cin >> a1 >> m1;
//标记是否有解
bool flag = false;
//因为已经读入一对a,m了，所以就循环n-1次就足够了
for(int i = 1; i < n; i++) {
ll a2, m2;
cin >> a2 >> m2;
//扩展欧几里得的计算
ll C = (m2 - m1), x0, y0;
ll d = exgcd(a1, a2, x0, y0);
//判断是否有解
if(C % d) {
flag = true;
break;
}
//计算答案
ll t = abs(a2 / d);
x0 %= t;
x0 = ((u128)x0 * C / d) % t;
m1 += x0 * a1;
a1 *= t;
}
if(flag) {
puts("-1");
}
else {
cout << (m1 % a1 + a1) % a1 << endl;
}
return 0;
}
