第十三届蓝桥杯省赛JavaA组 D 题、Java C 组 G 题、Python C 组 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
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair 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;
}

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/5885b0baf5.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐