C. Neko does Maths（code forces）

51 阅读 0 评论 34 点赞

我是靠谱客的博主无语纸飞机，最近开发中收集的这篇文章主要介绍C. Neko does Maths（code forces），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers ?a and ?b. His goal is to find a non-negative integer ?k such that the least common multiple of ?+?a+k and ?+?b+k is the smallest possible. If there are multiple optimal integers ?k, he needs to choose the smallest one.

Given his mathematical talent, Neko had no trouble getting Wrong Answer on this problem. Can you help him solve it?

Input

The only line contains two integers ?a and ?b (1≤?,?≤1091≤a,b≤109).

Output

Print the smallest non-negative integer ?k (?≥0k≥0) such that the lowest common multiple of ?+?a+k and ?+?b+k is the smallest possible.

If there are many possible integers ?k giving the same value of the least common multiple, print the smallest one.

思路：由于本题是让两数加上同时加上k，使得公倍数最小,我们把a、b用以下形式表示：a=x1*g+y，b=x2*g+y;其中g表示a和b共同的因子，y表示共同的余数，x1、x2表示他们各自的系数。，那么我们要做的其实就是把余数y补上k，使得
(a+k)%g==0,此时(b+k)%g也必定为0。a-b=g*(x1-x2),通过枚举a-b的因子来确定g从而确定

公倍数ans=num1*num2/gcd(num1,num2)。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include<iostream>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
ll num1,num2,tmp,k,minn,ans=0;
ll t1,t2;
ll gcd(ll a,ll b){
if(b==0)return a;
return gcd(b,a%b);
}
void ok(ll k){
ll tmp=((num1+k)*(num2+k))/(gcd(num1+k,num2+k));
if(minn>=tmp){
if(minn==tmp&&k<ans)ans=k;
ans=k;
minn=tmp;
}
}
int main(){
cin>>num1>>num2;
minn=num1*num2;
tmp=abs(num1-num2);
for(ll i=1;i*i<=tmp;i++){
if(tmp%i==0){
t1=i;
t2=tmp/i;
k=t1-(num1%t1);
ok(k);
k=t2-(num1%t2);
ok(k);
}
}
ok(0);
cout<<ans<<endl;
return 0;
}