https://www.luogu.com.cn/problem/P1082
题意概述：求 \(a\) 在模 \(b\) 意义下的逆元（\(b\) 不保证为质数，保证答案有解）。
运用拓展欧几里得算法求逆元，$ a x \equiv 1 \pmod {b}$ 等价于 $ ax = kb + 1 $，等价于 $ ax + by = 1$，求方程中 \(x\) 的最小正整数解。根据裴蜀定理，方程有整数解的充要条件是 \(a\)，\(b\) 互质。
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){ll a,b;cin >> a >> b;ll x,y;function<void(ll,ll)> exgcd = [&](ll a,ll b){if (b==0){x = 1;y = 0; }else{exgcd(b,a%b);ll tx = x;ll ty = y;x = ty;y = tx-a/b*ty; }};exgcd(a,b);x = (x%b+b)%b;cout << x << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}
https://www.luogu.com.cn/problem/P5656
题意概述：给定不定方程（丢番图方程）：$$ ax + by = c $$
如果方程无整数解，输出 \(-1\)。
如果方程有正整数解（\(x\)，\(y\) 能同时取到正整数），输出正整数解的数量，正整数解中 \(x\) 的最大值和最小值，\(y\) 的最大值和最小值。
如果方程无正整数解，输出整数解中 \(x\) 的最小正整数解，\(y\) 的最小正整数解。
令 \(d = gcd(a,b)\)，根据裴蜀定理，\(c\) 是 \(d\) 的倍数，否则无解。
首先考虑方程 \(ax + by = d\)，变换成原方程整体乘 \(c/d\) 即可。
用拓展欧几里得算法求得一组特解 \(x'\)，\(y'\)，则有：
\[x = x' + k \cdot (b/d)
\]
\[y = y' - k \cdot (a/d)
\]
\(k\) 为任意整数。
容易得到原方程的解为：
\[x = c/d \cdot x' + k \cdot (b/d)
\]
\[y = c/d \cdot y' - k \cdot (a/d)
\]
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){ll a,b,c;cin >> a >> b >> c;ll x,y,d;function<void(ll,ll)> exgcd = [&](ll a,ll b){if (b==0){d = a;x = 1;y = 0;}else{exgcd(b,a%b);ll tx = x;ll ty = y;x = ty;y = tx-a/b*ty; }};exgcd(a,b);if (c%d!=0){cout << -1 << '\n';return;}x *= c/d;y *= c/d;if (x<1){ll p = (1-x+b/d-1)/(b/d);x += b/d*p;y -= a/d*p;}else{ll p = (x-1)/(b/d);x -= b/d*p;y += a/d*p;}if (y<1){ll p = (1-y+a/d-1)/(a/d);cout << x << ' ' << y+a/d*p << '\n'; }else{ll p = (y-1)/(a/d);cout << p+1 << ' ' << x << ' ' << y-a/d*p << ' ' << x+b/d*p << ' ' << y << '\n';}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--) solve();return 0;
}