C. Neko does Maths（Gcd+数论）

C. Neko does Maths

思路：

x%k-y%k=0;

所以：abs(x-y)%k=0;

考虑y%x==0的情况，则lcm(x,y)=y(假设y最大)，所以k  = 0.

如果y%x!=0,假定y>x,(y-x)%k=0;

因为Gcd(x,y)=Gcd(y-x,x)=Gcd(y-x,y);

所以在这道题中y-x已经确定，只要找到满足条件的t即可，已知所有的k一定是y-x的因子。

求出所有k的因子，凑出(x+t)%k==0,t = x%t,因为要满足x>0，所以t = x-x%t.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
vector <LL> vc;
LL Gcd(LL x,LL y){
return y==0?x:Gcd(y,x%y);
}
LL lcm(LL x,LL y){
return x*y/Gcd(x,y);
}
void SP(LL &x,LL &y){
LL tp = x;
x = y;
y = tp;
}
void get_f(LL x){
vc.clear();
for(LL i=1;i<=sqrt(x);i++)
if(x%i==0){
vc.push_back(i);
if(i*i!=x) vc.push_back(x/i);
}
}
int main(void)
{
LL x,y;
scanf("%lld%lld",&x,&y);
if(x>y) SP(x,y);
if(y%x==0){
printf("0n");
return 0;
}
LL cha = y-x;
get_f(cha);
int len = vc.size();
LL ans = 0,tmp = 1e18+10;
for(int i=0;i<len;i++){
LL tt = 0;
if(x%vc[i]){
tt = vc[i]-x%vc[i];
}
//printf("%lld . ",tt);
LL tp = lcm(x+tt,y+tt);
if(tp<tmp){
tmp = tp;
ans = tt;
}
}
printf("%lldn",ans);
return 0;
}

最后

以上就是无聊豆芽为你收集整理的C. Neko does Maths（Gcd+数论）的全部内容，希望文章能够帮你解决C. Neko does Maths（Gcd+数论）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。