数论

【蓝桥杯 2022】GCD

Posted by WHZ0325 on 2023-03-25, Viewed times

题目描述

求最小的 $k$，使得 $gcd(a+k,b+k)$ 的值最大。

$1\le a\lt b\le 10^{18}$。

算法分析

数论忘光了，思博选手不会写数学题。。。

首先有 $gcd(a,b)=gcd(b,a-b)$，很好理解：$a=gc$，$b=gd$ 的话 $a-b=g(c-d)$ 依然是两者最大公约数的倍数，这就是辗转相除法的基础。

那么，有 $gcd(a+k,b+k)=gcd(a-b,a+k)$ 且 $gcd(a+k,b+k)=gcd(a-b,b+k)$，一定能构造出 $g=a-b$ 的解，取 $a-b|a+k$ 和 $a-b|b+k$ 中最小的 $k$ 即可。

代码实现

1
2
3
4
5
6
7
8
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long a = in.nextLong(), b = in.nextLong(), d = Math.abs(a - b);
        System.out.println(Math.min(d - a % d, d - b % d));
    }
}