题目链接:https://codeforces.com/contest/1152/problem/C

题目大意:给定两个正整数a,b,其中(1<=a,b<=1e9),求一个正整数k(0<=k),使得a+k与b+k的最小公倍数最小。

解题思路:首先我们需要知道gcd(a,b)=gcd(a,b-a)=gcd(b,b-a)(b>a)的

我们要求的是lcm(a+k,b+k)=(a+k)(b+k)/gcd(a+k,b+k)=(a+k)(b+k)/gcd(a+k,b-a)

因为b-a是定值,所以我们可以枚举每个b-a的约数设为x,然后我们计算出最小的k使得(a+k)%x==0,然后计算他们的最小公倍数,如果大于我们的当前最小公倍数就更新。

代码:

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int maxn=2e5+;
vector<ll> yinzi;
int main(){
ll a,b;
cin>>a>>b;
if(a>b)swap(a,b);
if(a==b||b%a==||b-a==){
cout<<<<endl;
return ;
}
int cha=b-a;
for(int i=;i*i<=cha;i++){ //计算b-a的所有因子
if(cha%i==){
yinzi.push_back(i);
if(i*i!=cha) yinzi.push_back(cha/i);
}
}
ll ans=lcm(a,b),x=;
for(int i=;i<yinzi.size();i++){
int k=;
if(a%yinzi[i]) k=yinzi[i]-a%yinzi[i];
if(k>=){
ll tmp=(a+k)/yinzi[i]*(b+k);
if(tmp==ans&&k<x) x=k;
if(tmp<ans){
ans=tmp;
x=k;
}
}
}
cout<<x<<endl;
return ;
}

最新文章

  1. [转] How to debug a ARM Cortex-M hard fault exception
  2. Webform(分页与组合查询配合使用)
  3. Angular JS中的依赖注入
  4. 29.调整数组顺序使奇数位于偶数前面[ReOrderArray]
  5. android FragmentPagerAdapter getItem方法没有执行
  6. Java SE技术概览 - Jave SE Platform at a Glance
  7. 随便写写,当作了解--Css
  8. 格式化URL
  9. Android上使用OpenGLES2.0显示YUV数据
  10. linux中screen命令的用法
  11. 小技巧,把execl.exe转换成dll
  12. Django 学习第十一天——中间键和上下文处理器
  13. amqp笔记
  14. word之高级
  15. Struts2 使用Jquery+ajax 文件上传
  16. Mac系统下安装PyCharm
  17. Wix制作安装包
  18. 混合pyqt和qtcreator
  19. Android-Kotlin简单计算器功能
  20. sqli-labs学习(less-5-less-7)

热门文章

  1. service pom
  2. Linux find过滤掉没有查看权限的文件
  3. 4412 移植x264并且YUV422转x264
  4. B/S大文件断点续传
  5. c++读取数据
  6. [CSP-S模拟测试97]题解
  7. sql常用 语句总结
  8. 2019牛客暑期多校训练营(第九场)H Cutting Bamboos(主席树+二分)
  9. Day1 方法的重载
  10. (转)深入理解Linux修改hostname