[ 东莞市选 2008 ] GCD&LCM

\(\\\)

\(Description\)

给出两数的\(GCD\)和\(LCM\)，求合法的两数之差的绝对值最小是多少。

\(GCD\times LCM\le10^{18}\)

\(\\\)

\(Solution\)

多解的有趣小水题。

\(\\\)

解法一：求出\(GCD\times LCM\)，我们知道这个就等于两数之积，考虑枚举其中的一个数。

考虑枚举的数一定是\(GCD\)的倍数，所以直接枚举就好，我们只需要处理枚举的数小于另一个数的情况，最后将所有算出来的答案取\(min\) 即可，复杂度 \(\text O(\sqrt{LCM})\)。

\(\\\)

解法二：\(\frac{LCM}{GCD}=\frac A{GCD}\times \frac B{GCD}\)枚举第二个式子左半部分，乘上更新答案。复杂度\(\text O(\sqrt{\frac{LCM}{GCD}})\)

\(\\\)

解法三：还是上面的式子。考虑当\(\frac A{GCD}\)和\(\frac B{GCD}\)最接近的时候产生的差值最小所以直接从\(\sqrt{\frac{LCM}{GCD}}\)处开始枚举第一个遇见的答案一定是最优秀的。

\(\\\)

\(Code\)

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

typedef long long ll;

ll a,b,ans=900000000000000ll;

inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

int main(){

  scanf("%lld%lld",&a,&b);

  b*=a;

  for(R ll i=a,j;i<=b;i+=a){

    if(b%i!=0) continue;

    j=b/i; if(i>j) break;

    if(gcd(i,j)==a) ans=min(ans,j-i);

  }

  printf("%lld\n",ans);

  return 0;

}

巴特西

[ 东莞市选 2008 ] GCD&LCM

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章