原题链接:蓝桥杯2022年第十三届省赛真题-GCD
解题思路:
注意事项:
参考代码:
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 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复