第十三届蓝桥杯省赛JavaA组 D 题、Java C 组 G 题、Python C 组 G题——GCD（AC）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
1.GCD
1.题目描述
给定两个不同的正整数
a
,
b
a,b
a,b 求一个正整数
k
k
k 使得
g
c
d
(
a
+
k
,
b
+
k
)
gcd(a+k,b+k)
gcd(a+k,b+k) 尽可能 大,其中
g
c
d
(
a
,
b
)
gcd(a,b)
gcd(a,b) 表示
a
a
a 和
b
b
b 的最大公约数如果存在多个
k
k
k, 请输出所有满 足条件的
k
k
k 中最小的那个。
2.输入格式
输入一行包含两个正整数 a , b a,b a,b, 用一个空格分隔。
3.输出格式
输出一行包含一个正整数 k k k 。
4.样例输入
5 7
5.样例输出
1
6.数据范围
1 ≤ a < b ≤ 1 0 18 1≤a<b≤10^{18} 1≤a<b≤1018
7.原题链接
2.解题思路
熟悉gcd的性质的话根据更相减损术可以知道一个等式
g
c
d
(
a
,
b
)
=
g
c
d
(
a
,
b
−
a
)
gcd(a,b)=gcd(a,b-a)
gcd(a,b)=gcd(a,b−a)
当然这里前提是
b
>
=
a
b>=a
b>=a同样根据该式我们可以将题目给定的原式进行变形:
g
c
d
(
a
+
k
,
b
+
k
)
=
g
c
d
(
a
+
k
,
b
−
a
)
gcd(a+k,b+k)=gcd(a+k,b-a)
gcd(a+k,b+k)=gcd(a+k,b−a)
因为
a
,
b
a,b
a,b 都是已知的我们令
c
=
b
−
a
c=b-a
c=b−a当然此时需要保证b>=a那么我们求的式子就变为了
g
c
d
(
a
+
k
,
c
)
gcd(a+k,c)
gcd(a+k,c)显然这个式子的最大gcd一定为
c
c
c我们只需要计算出
a
a
a 最少需要增加多少可以成为
c
c
c 的倍数这个增量即是答案
k
k
k 。
时间复杂度
O
(
1
)
O(1)
O(1)
3.Ac_code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
LL a, b;
void solve()
{
cin >> a >> b;
if (a > b) swap(a, b);
LL c = b - a;
LL g = a / c;
if (a % c) g++;
cout << (g * c - a) << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}