安徽网站开发培训价格,在线音乐网站开发php,做网站能赚到流量费吗,个人网站备案要什么GCD与LCM
题目大意#xff1a;
给出a,b的最大公因数和最小公倍数#xff0c;求出符合条件的a,b的最小差值
样例输入
6 36
样例输出
6
数据范围限制
提示
数据说明#xff1a;
对于50%的数据#xff0c;1ab10^3。
对于100%的数据#xff0c;1a
给出a,b的最大公因数和最小公倍数求出符合条件的a,b的最小差值
样例输入
6 36
样例输出
6
数据范围限制
提示
数据说明
对于50%的数据1ab10^3。
对于100%的数据1ab10^9。
解题思路
先用最小公倍数除以最大公因数得出a,b已经除过最大公因数的乘积然后分解质因数将相同的乘在一起再用dfs分配到两边求出最小的差最后还要乘上最大公因数
#includecstdio
#includeiostream
using namespace std;
long long n,m,t,num,ans,a[10005];
int w,o;
long long minn(long long xx,long long yy)//求最小的
{if (xxyy) return xx;return yy;
}
void dfs(long x,long y,int dep)//分配
{if (depw){if (xy) ansminn(ans,x-y);//要使差是整数else ansminn(ans,y-x);return;}dfs(x*a[dep],y,dep1);//分配给左边dfs(x,y*a[dep],dep1);//分配给右边
}
int main()
{scanf(%lld %lld,n,m);tm/n;num2;while(t!1)//没有除完if (t%num0) //可以整除{t/num;//除if (o) a[w]*num;//已经有同样的数就乘在一起避免不是互质else a[w]num,o1;//没有同样的数自己单独一个}else num,o0;//除数ans9223372036854775807;//long long的范围2^63-1dfs(1,1,1);//dfs分配printf(%lld,ans*n);//乘上最大公因数return 0;
}