第十三届蓝桥杯省赛JavaA组D题、JavaC组G题、PythonC组G题——GCD（AC）

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.原题链接

GCD

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; }