给两个正整数 \(a, b\) ,可以执行以下操作之一任意次:
- \(a = a + 1, b = b + 1\) 。
- \(a = a - 1, b = b - 1\) 。
需要保证 \(min(a, b) \geq 0\) 。
询问 \(gcd(a, b)\) 最大是多少,且到达最大 \(gcd(a, b)\) 最少需要多少步。
不妨让 \(b \leq a\) 。
观察:\(a, b\) 都会变动,无法直接讨论 \(gcd(a, b)\) 。但 \(a - b\) 恒不变。
根据辗转相除法,有 \(gcd(a, b) = gcd(b, a - b)\) 。
- 当 \(b = 0\) ,\(gcd(b, a - b) = a - b\) 。
- 当 \(b \neq 0\) ,\(gcd(b, a - b) = min(b, a - b)\) 。
于是 \(gcd(a, b)_{max} = a - b\) 。
注意 \(gcd\) 不能为 \(0\) 。于是若 \(a - b = 0\) ,则 \(gcd(a, b)_{max} = inf\) 。
当 \(gcd(a, b)\) 达到 \(max\) ,令 \(g = a - b\) ,有 \(g \mid a\) , \(g \mid b\) 。
令 \(r\) 满足 \(b \equiv r (\mod g)\) ,此时需要调整的次数为 \(r\) 或者 \(g - r\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
ll a, b; std::cin >> a >> b;
if (a < b) std::swap(a, b);
ll g = a - b;
if (g == 0) std::cout << 0 << ' ' << 0 << '\n';
else std::cout << g << ' ' << std::min(b % g, g - b % g) << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}