解题思路:
注意事项:
参考代码:
import java.util.Scanner; /** * * 最大公约数的一个关键性质是: * * 两个数的最大公约数与它们的差值的最大公约数是相同的。 * 题目给出:当b>a时 * gcd(a,b)=gcd(a,b-a) * gcd(a+k,b+k)=gcd(a+k,b-a)=x * 由公因数性质,此时有: * (a+k)%x=0 * (b-a)%x=0 * 则该gcd的结果【最大值】不能大于b-a, 因为b-a是其中一个值 * 反正不管怎么样,就是不能大于b-a,不用考虑a+k与b-a的大小关系 * 所以要使得gcd(a+k,b+k),尽可能大,那么就取这个结果为 b-a 这个最大值 * 所以a+k需要满足是b-a的倍数,算出满足(a+k)%(b-a)=0,k的最小值即可 * k=(b-a)*m - a m为整数 * 且存在:k>0 * 则(b-a)*m - a >0 * 即m>a/(b-a) * */ public class Main { static long a; static long b; static long k; public static void main(String[] args) { Scanner sc = new Scanner(System.in); a = sc.nextLong(); b = sc.nextLong(); long c = b - a; long m=0; if(a%c==0){ m=a/c; }else{ m=a/c+1; } k = c*m -a; System.out.println(k); } }
0.0分
0 人评分