Problem: M题 Water

题意

• 给两个容量分别为$A\mathrm{，}BA，B$的杯子
• 给以下四种操作：
  • 将$AA$或$BB$注满水
  • 将$AA$或$BB$中水倒掉
  • 喝光$AA$或$BB$杯子中的水
  • 将$AA$杯子中水倒进$BB$或将$BB$杯子中水倒进$AA$
• 求每次用上述四种方法的一种，最少几次可以喝$xx$水（如果不能输出$-1-1$）

思路

题目就是任意$A,-A,+B,-BA,\; -A,\; +B,\; -B$的和等于$xx$，即$rA+sB=xrA\; +\; sB\; =\; x$，对于这个式子，由裴蜀定理有如果$x\mathrm{\%}gcd(A,B)!=0x\; \backslash \%\; gcd(A,\; B)\; !=\; 0$，此题无解。当此题有解时，而对于式子$rA+sB=xrA\; +\; sB\; =\; x$求解$r\mathrm{、}sr、s$可用拓展欧几里得算法$(exgcd)(exgcd)$。
发现当求解出$r>=0,s>=0r>=0,s\; >=\; 0$,我们操作一定是装$AA$喝$AA$，装$BB$喝$BB$，直到满足喝$r\ast A,s\ast Br\; *\; A,\; s\; *\; B$，这样我们的操作数就是$2\ast (r+s)2\; *\; (r\; +\; s)$。
如果，不妨令。则我们操作是，先装$AA$，将$AA$倒入$BB$中，如果$BB$满了，就把$BB$倒掉，直到将装满过$ss$个$BB$，同时最后一个$BB$可以不倒，这样我们的操作数就是$2\ast (r+abs(s))-12\; *\; (r\; +\; abs(s))\; -\; 1$。

解题方法

我们先用$exgcdexgcd$求出$r\mathrm{、}sr、s$，因为我们算最小操作数的式子$2\ast (r+s)2\; *\; (r\; +\; s)$和$2\ast (r+abs(s))-12\; *\; (r\; +\; abs(s))\; -\; 1$，我们需要在$rr$接近$00$或者$ss$接近$00$时，可以得到最优解。（$rr$就是操作$AA$的次数，$ss$就是操作$BB$的次数，我们自己玩一玩是不是也可以感觉到越接近于只用一种杯子，就可以用更少的次数）

复杂度

• 时间复杂度:

每次$exgcdexgcd$得到$r\mathrm{，}sr，s$，然后只在$00$点附近跑很小的范围，因此每次查询复杂度是$O(logn)O(logn)$，总复杂度就是$O(nlogn)O(nlogn)$

• 空间复杂度:

没有数组，复杂度是常量级的$O(1)O(1)$

Code

#include <bits/stdc++.h>

#pragma GCC optimize(2)
using namespace std;

#define endl "\n"
#define 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, x;
	cin >> a >> b >> x;

	ll r, s;
	ll d = exgcd(a, b, r, s);

	if(x % d) return cout << -1 << endl, void();

	a /= d, b /= d, x /= d, r *= x, s *= x;
    
	ll ans = 1e18;
	
    //在附近取值
	auto getans = [&](ll t){
		ll n = r + t * b, m = s - t * a;
		if(n >= 0 && m >= 0) ans = min(ans, 2 * (n + m));
		else ans = min(ans, 2 * abs(n - m) - 1);
	};

	ll t0 = -r / b;
	for(int i = t0 - 1; i <= t0 + 1; i++) getans(i);
	t0 = s / a;
	for(int i = t0 - 1; i <= t0 + 1; i++) getans(i);

	cout << ans << endl;
}

int main()
{
	cout.tie(nullptr);cin.tie(nullptr);ios::sync_with_stdio(false);

	int _ = 1;
	cin >> _;
	while (_--) solve();

	return 0;
}

PS：欢迎大家批评指正