原题链接:蓝桥杯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、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复