题目

给定两个不同的正整数 a,ba,b, 求一个正整数 kk 使得 gcd(a+k,b+k)gcd(a+k,b+k) 尽可能 大, 其中 gcd⁡(a,b)gcd(a,b) 表示 aa 和 bb 的最大公约数, 如果存在多个 kk, 请输出所有满 足条件的 kk 中最小的那个。

输入格式

输入一行包含两个正整数 a,ba,b, 用一个空格分隔。

输出格式

输出一行包含一个正整数 kk 。

样例输入

1
5 7

样例输出

1
1

评测用例规模与约定

对于 20%20% 的评测用例， a<b≤105a<b≤105;

对于 40%40% 的评测用例, a<b≤109a<b≤109;

对于所有评测用例, 1≤a<b≤10181≤a<b≤1018 。

解题思路

找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
a,b = (1, 2)gcd = 1
K = 1
a,b = (1, 3)gcd = 1
K = 1
a,b = (1, 4)gcd = 1
K = 2
a,b = (2, 3)gcd = 1
K = 1
a,b = (2, 4)gcd = 2
K = 2
a,b = (2, 5)gcd = 1
K = 1
a,b = (3, 4)gcd = 1
K = 1
a,b = (3, 5)gcd = 1
K = 1
a,b = (3, 6)gcd = 3
K = 3
a,b = (4, 5)gcd = 1
K = 1
a,b = (4, 6)gcd = 2
K = 2
a,b = (4, 7)gcd = 1
K = 2
a,b = (5, 6)gcd = 1
K = 1
a,b = (5, 7)gcd = 1
K = 1
a,b = (5, 8)gcd = 1
K = 1
a,b = (6, 7)gcd = 1
K = 1
a,b = (6, 8)gcd = 2
K = 2
a,b = (6, 9)gcd = 3
K = 3
a,b = (7, 8)gcd = 1
K = 1
a,b = (7, 9)gcd = 1
K = 1
a,b = (7, 10)gcd = 1
K = 2
a,b = (8, 9)gcd = 1
K = 1
a,b = (8, 10)gcd = 2
K = 2
a,b = (8, 11)gcd = 1
K = 1
a,b = (9, 10)gcd = 1
K = 1
a,b = (9, 11)gcd = 1
K = 1
a,b = (9, 12)gcd = 3
K = 3

这题就是一道找规律，需要自己写一个暴力破解K，然后输出用例自己找规律。

代码

1
2
3
4
In = input().split()
a, b = map(int, In)
c = abs(a - b)
print(c - (a % c))