AcWing 4659. GCD
原题链接
简单
作者:
CqAq
,
2024-03-30 17:34:54
,
所有人可见
,
阅读 15
算法1
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;
int main()
{
ll a, b; cin >> a >> b;
//gcd(a + k, b + k);的最大值----在最大公约数中gcd(a,b)=min(a,b);\
或gcd(x, x + phi);中x和x + phi的最大公约数不超过phi。\
且最大为phi,所以phi为x的公约数时,取最大(x + phi) % phi = 0 + 0 = 0;\
在a,b中abs(a - b) = phi, 所以要满足min(a,b) % phi = 0;
if(a > b) swap(a, b);
ll phi = b - a;
ll m = a / phi, mm = a % phi;
if(mm) m ++;
ll ans = m * phi - a;
cout << ans;
return 0;
}