思路:

假设a <= b,lcm(a + k, b + k) = (a + k) * (b + k) / gcd(a + k, b + k) = (a + k) * (b + k) / gcd(b - a, a + k)(根据gcd(a, b) = gcd(b - a, a)),所以枚举b - a的所有因子即可。

实现:

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll cal(ll x, ll y, ll i, ll & minn, ll & ans)
{
if (i > x)
{
if (y + i - x < minn)
{
minn = y + i - x;
ans = i - x;
}
}
else
{
ll k = ;
if (x % i) k = (x / i + ) * i - x;
ll t = (x + k) * (y + k) / __gcd(y - x, x + k);
if (t < minn)
{
minn = t;
ans = k;
}
}
}
int main()
{
ll a, b;
while (cin >> a >> b)
{
ll x = min(a, b), y = max(a, b);
if (y % x == ) { cout << << endl; continue; }
ll minn = INF, ans = ;
for (int i = ; i * i <= y - x; i++)
{
if ((y - x) % i == )
{
cal(x, y, i, minn, ans);
if ((y - x) / i != i) cal(x, y, (y - x) / i, minn, ans);
}
}
cout << ans << endl;
}
return ;
}

最新文章

  1. nyoj412_bitset_
  2. matlab实现感知机算法--统计学习小灶
  3. Android--自动搜索提示
  4. html中设置锚点定位的几种常见方法(#号定位)
  5. Ecological Premium
  6. FreeModbus Slave RTU 精简版源代码【worldsing 笔记】
  7. 1、CentOS6.5系统安装及学习
  8. PHP常用字符串函数
  9. 安装centos7注意事项
  10. C#可扩展编程之MEF
  11. Css 之 px em %
  12. Elixir游戏服设计二
  13. RSA非对称加密简析-java
  14. “Validation failed for one or more entities”异常的解决办法
  15. export ,export default 和 import 区别 以及用法
  16. 【OS】Process &amp; Thread
  17. [USACO07OPEN]便宜的回文Cheapest Palindrome
  18. ThreadLocal源码调试——“this”作为key
  19. jquery-Ajax请求用例码
  20. crontab定时

热门文章

  1. 应用HtmlInputFile进行大文件上传 解决asp.net上传大文件默认文件大小限制
  2. 错误:Tomcat version 7.0 only supports J2EE 1.2, 1.3, 1.4, and Java EE 5 and 6 Web
  3. ASP.NET 调试出现&lt;%@ Application Codebehind=&quot;Global.asax.cs&quot; Inherits=&quot;XXX.XXX.Global&quot; Language=&quot;C#&quot; %&gt;
  4. cocos2dx之lua绑定简析
  5. Codeforces 92C【二分】
  6. java整理(二)
  7. 通过jQuery实现AJAX
  8. Objective-C对象的申请空间与初始化
  9. 洛谷P1505 [国家集训队]旅游
  10. ELK系列(2) - Kibana怎么修改日期格式Date format