lizuwangCode


私信TA

用户名:dotcpp0719174

访问量:167

签 名:

等  级
排  名 34233
经  验 446
参赛次数 0
文章发表 2
年  龄 0
在职情况 学生
学  校 广西大学
专  业

  自我简介:

解题思路:

注意事项:

参考代码:

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 人评分

  评论区

  • «
  • »