AcWing 4659. GCD
原题链接
简单
作者:
不知名的fE
,
2025-01-17 11:43:36
,
所有人可见
,
阅读 3
import java.util.Scanner;
public class Main {
/*
相差为sub的最大gcd(a, b) = d => gcd(a, a + sub) = d
a % d == 0 && sub % d == 0
令a = x0 + k
因此要保证a%d=0和差值sub%d=0,其中a%d=0可以变为(x0 + k) %d == 0
也就是保证(x0 + k) %d == 0, 差值sub % d == 0
根据上面两个公式可以得到:sub约数d,x0约数k
也就是d<=sub即d的最大值为sub,将其带入到第一个式子:
(x0 + k) % sub == 0可以得出k的最小正整数值为
min(k) = ceil(x0 / sub) * sub - x0;//ceil上取整
要注意的是k为0的时候取sub
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long a = sc.nextLong(), b = sc.nextLong();
System.out.println(get(Math.min(a, b), Math.abs(a - b)));
sc.close();
}
static long get(long x0, long sub) {
long ans = (x0 + sub - 1) / sub * sub - x0;
return ans == 0 ? sub : ans;
}
}