这道题虽然简单,但是很绕,花了我不少时间去理清楚
首先就是明确目标,我们要求的是gcd(a + k, b + k)
而这里我们就涉及到一个原始的独特算法-----更相减损术
更相减损术
- 如一个gcd(20, 4) <=> gcd(4, 20 - 4 = 16) 用较大数减去较小数
- 但这样子还是看不出来最大公约数是谁,于是继续下去:gcd(4, 16) <=> gcd(4, 16 - 4 = 12) <=> gcd(4, 12 - 4 = 8) <=> gcd(4, 8 - 4 = 4)
- 直到出现gcd(a, a),显而易见的两个相同数的最大公约数就是这个相同数
- 而为什么这样子成立?因为如果a和b的最大公约数是g,那么a和b都能被g整除。也就是说,存在 m 和 n使得恒成立
a = g * m
,b = g * n
,且 m 和 n 是两个常数。 - 因此,a - b也应该能被g整除,因为:
𝑎−𝑏 = 𝑔⋅𝑚 − 𝑔⋅𝑛 = 𝑔⋅(𝑚−𝑛)
所以,a - b与b的最大公约数仍然是g。
通过不断地将较大数减去较小数,我们实际上是在不断缩小这两个数(原来的a, b)的差,最终减到它们的最大公约数
好,了解了更相减损术就进入实战环节:
gcd(a + k, b + k) <=> gcd(|(a + k) - (b + k)| = |a - b|, b + k)
此时我们很惊奇的发现,gcd()中原本两个变量转化成了只有一个变量,而另一个是固定值!
这有什么用呢?
设gcd(|a - b|, b + k) = p, 那么p既是|a - b|的约数又是b + k的约数,由上述得到p是绝对小于等于
|a - b|这个定值的,因为某个数x的约数y是属于(1, x)的区间的
此时我们就知道,为了使b + k与|a - b|的“最大”“公约数”尽可能大,那么p就应该是在(1, |a - b|)区间内的最大的数即|a - b|,且p也得是b + k的约数,那么b + k就得是p的倍数也即|a - b|的倍数
数学上这么表示b + k 是 |a - b|的倍数:
b + k ≡ 0 mod |a - b|
-> k ≡ -b mod |a - b|, 其中c是整数,这是一条同余的变换式
模运算结果不出现负数:
1. 模运算的本质
给定一个整数 b 和一个正整数 d,b % d表示的是b除以d后得到的余数。这个余数r满足:
𝑏=𝑞⋅𝑑+𝑟
其中,q是商,r是余数,并且:
0≤𝑟<𝑑
这个余数 r 就是 b % d。
2. -b等于b % d
对于-b的模运算, -b % d表示的是-b除以d后的余数。我们可以通过一些步骤来理解这个结果。
a. 负数的余数
我们先看看负数是如何进行模运算的。设 b = 7 和 d = 5。我们知道:
7%5=2
这是因为:
7=5⋅1+2
现在,我们来计算 -7 % 5。为了得到这个余数,我们可以这么做:
−7=5⋅(−2)+3
也就是说,-7除以5的余数是3。也可以理解为:
−7%5=3
这个结果是一个非负的余数,满足0 <= 3 < 5。
b. 通用结论
对于任何整数b,-b % d可以通过以下步骤推导:
假设b = q * d + r,其中r = b % d,0 <= r < d。
那么:
−𝑏=−(𝑞⋅𝑑+𝑟)=−𝑞⋅𝑑−𝑟
如果我们计算-b % d,其实是寻找-r在模d下的非负余数。因为-r是负数,我们希望将其转换成非负余数。为了做到这一点,我们加上d,得到:
−𝑟+𝑑=𝑑−𝑟
所以:
−𝑏%𝑑=𝑑−(𝑏%𝑑)
3. 结论
所以,-b % d 的结果是 d - (b % d)。这个结果使得余数是非负的,并且在0到d-1之间
公式由上推导而来
a, b = map(int, input().split())
print(abs(a - b) - a % abs(a - b))