jzojGCD与LCM【辗转相除法】【短除法】

>Description
给出某两个数的最大公因数和最小公倍数,要求求出在两数之间的差最小的情况下,这两个数的值。


>Input
输入n,m。表示最大公因数n,与最小公倍数m。

>Output
输出这两个数的差。


>Sample Input
6 36

>Sample Output
6


>解题思路
按照短除法
jzojGCD与LCM【辗转相除法】【短除法】
12和18为上面6和36所求的数,最大公因数6为红色字体2 * 3,最小公倍数36为红色字体2 * 3再*黑色字体2 * 3,所以用最小公倍数除以最大公因数就可以得到下面黑色字体的乘积,把这个存进r变量,循环r的开方,在一个一个枚举这两个数,加上一些特殊判断就OK了。


>代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int l,r,n,m,ans;
int ooo(int x,int y)
{
	if(x%y==0) return y;
	else return(ooo(y,x%y));
} //辗转相除法
int main()
{
	ans=2147483647;
	scanf("%d%d",&n,&m);
	r=m/n;
	l=(floor)(sqrt(r));
	for(int i=1;i<=l;i++)
	{
		int a=i,b=r/a; //枚举下面两个数
		if(r%a!=0) continue; //当a不为r的因数时continue
		if(ooo(a*n,b*n)!=n) continue; //辗转相除法算出a,b的最大公因数
		ans=min(ans,b*n-a*n); //min一下
	}
	printf("%d",ans);
	return 0;
}
上一篇:ZOJ 2342 - 简单思维题


下一篇:洛咕 【P1891】疯狂LCM & 三倍经验