蓝桥杯2022年第十三届省赛真题-GCD

解题思路:

//考察gcd性质，根据更相减损术可以知道一个等式：gcd(a,b)=gcd(a,b-a)  当然这里的前提时a<=b;

//所以gcd(a+k,b+k)=gcd(a+k,b-a)  这里的a和b都是已知的  

//我们可以设c=b-a    即c是已知的  所以想要使得a+k与c的最大公因子尽可能地大  因为最大最大能到达c 

//显然这个式子的最大gcd一定为 c ,我们只需要计算出a 最少需要增加多少可以成为 c 的倍数，这个增量即是答案k   

注意事项:

参考代码:

#include<iostream>

using namespace std; 

long long a,b,c,g;

int main()

{

cin>>a>>b;

if(a>b) swap(a,b);

c=b-a;

g=a/c;

if(a%c) g++;

cout<<g*c-a<<endl;

}