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

客官°小女子只卖身不卖艺 2023-09-29 00:27 7阅读 0赞

## 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.样例输出 ###

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

[GCD]: https://www.lanqiao.cn/problems/2133/learning/