博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
GCD与LCM【数论】
阅读量:5127 次
发布时间:2019-06-13

本文共 803 字,大约阅读时间需要 2 分钟。

题目大意:

给出两个数的GCDGCDLCMLCM,求这两个数的最小差值。
IuputIuput

6 36

OutputOutput

6

思路:

一道数论题。
我们设这两个数分别为xxyyxyx≤yg=gcd(x,y)g=gcd(x,y)l=lcm(x,y)l=lcm(x,y),那么必然有

l=xg×yg×gl=xg×yg×g
l=xygg2l=xygg2
约分得
l=xygl=xyg
移项得
lg=xylg=xy
由于
gg必然是
xx的因数,所以可以设
k=gxk=gx,则
x=kgx=kg
带入上式,得
lg=kgylg=kgy
,
根据等式的性质,得
lg=kglklg=kglk
那么只要枚举
kk,我们就可以求出正确答案了。


代码:

#include 
#include
#include
using namespace std;long long g,l,x,y,z,ans;int main(){ scanf("%d%d",&g,&l); for (long long i=1;1;i++) { if (g*i>l/i) return printf("%d\n",ans)&0; //当a>b时,程序结束 if (l%i) continue; //l不能整除i(即上文所述k) x=g*i; y=l/i; //求出两数的值 z=__gcd(x,y); if (z==g&&x*y==g*l) ans=l/i-i*g; //判断是否成立 }}

转载于:https://www.cnblogs.com/hello-tomorrow/p/9313038.html

你可能感兴趣的文章
display:none和visiblity:hidden区别
查看>>
C#double转化成字符串 保留小数位数, 不以科学计数法的形式出现。
查看>>
牛的障碍Cow Steeplechase
查看>>
Zookeeper选举算法原理
查看>>
3月29日AM
查看>>
利用IP地址查询接口来查询IP归属地
查看>>
HTML元素定义 ID,Class,Style的优先级
查看>>
构造者模式
查看>>
http和https的区别
查看>>
Hbuild在线云ios打包失败,提示BuildConfigure Failed 31013 App Store 图标 未找到 解决方法...
查看>>
找到树中指定id的所有父节点
查看>>
今天新开通了博客
查看>>
AS3优化性能笔记二
查看>>
ElasticSearch(站内搜索)
查看>>
4----COM:a Generative Model for group recommendation(组推荐的一种生成模型)
查看>>
UVA 11137 - Ingenuous Cubrency
查看>>
js阻止事件冒泡的两种方法
查看>>
Java异常抛出
查看>>
[SQL Server 系] T-SQL数据库的创建与修改
查看>>
74HC164应用
查看>>