Water(擴歐求特解與通解)
題意：給容量分別為A與B的水杯，問確切喝到C水的最小操作次數(shù)
有4種操作：選一杯全喝，選一杯全部倒掉，選一杯裝滿，將一杯的水盡量倒到另一杯中
思路：只有Ax+By=C有解時才能確切喝到X水
裴蜀定理：如果a、b是整數(shù)，那么一定存在整數(shù)x、y使得ax+by=k*gcd(a,b)。
思路：要求x，y的特解，可以使用exgcd的板子，令c = k * gcd(A, B)則Ax + By = c;exgcd求出來的是k = 1時的特解
只要將x *= c / gcd(A, B)， y *= c / gcd(A, B)；此時x和y就是方程Ax + By = c的特解
這里有一個步長的概念對于x他的步長是 B / gcd(A, B)， 對于y他的步長是 A / gcd(A, B)
要求最小整數(shù)解，只需要把x除上他的步長就能知道x要走多少步才能最接近0，再把x -= 步長 * 步數(shù)就可以讓x最接近0，然
后在對原點附近的 (x?+t?步長,y??t?步長)求min?即可得到最小整數(shù)解

#include<bits/stdc++.h>
using namespace std;#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
typedef pair<int, int> pr;#define int long long
#define ll long long
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define ufr(i,n,z) for(int i = n;i >= z; i--)
#define pb(x) push_back(x)
#define all(a) a.begin(),a.end()
#define fi first
#define se secondconst int N = 1e6 + 10;
const int mod = 998244353, inf = LONG_LONG_MAX;
int dx[] = { 0,0,-1,0,1 }, dy[] = { 0,-1,0,1,0 };
int n, m;int a[N];
int gcd(int a, int b) { ? ? ? ? //輾轉(zhuǎn)相除return !b ? a : gcd(b, a % b);
}
int exgcd(int a, int b, int& x, int& y) ? ? ? //擴歐板子
{if (b == 0) {x = 1; y = 0;return a; ?//到達遞歸邊界開始向上一層返回}ll d = exgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}
void solve()
{int a, b, c;cin >> a >> b >> c;if (c % gcd(a, b) != 0) {cout << -1 << '\n'; ? ? ? ? ? ? ? ? ?//無解}else {int x, y;int d = exgcd(a, b, x, y);x *= c / d; y *= c / d; ? ? ? ? ? ? ? ? ? ?//特解(除去最大公約數(shù)乘上C)int dx = b / d; int dy = a / d;y += (x / dx) * dy;x -= (x / dx) * dx; ? ? ? //最小整數(shù)解，只需要把x除上他的步長就能知道x要走多少步才能最接近0int ans = inf;fr(i, -10, 10) {int xx = x + dx * i; int yy = y - dy * i; ? ? ? ? ? //通解ans = min(ans, max((xx + yy) << 1, (abs(xx - yy) << 1) - 1));}cout << ans << '\n';}
}signed main()
{// ? ?ios;int t = 1;cin >> t;while (t--) solve();return 0;
}

P1082 [NOIP2012 提高組] 同余方程
題意:求ax->1(mod b)的最小整數(shù)解，輸入數(shù)據(jù)保證一定有解。
轉(zhuǎn)變?yōu)閍x=1+by,移項ax-by=1,

擴歐求的特解x/d,y/d,

通解x/d-i*(x/d/b/d)*b/d->x/d-x/b*(b/d)->x/d-i*x/d
?

#include<iostream>
#define int long long
using namespace std;
int exgcd(int a, int b, int& x, int& y) {if (b == 0) {x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}
signed main(){int a, b;int x, y;cin >> a >> b;exgcd(a, b, x, y);cout << (x % b + b) % b << '\n';return 0;
}