GCD與LCM

題目大意：

給出a,b的最大公因數和最小公倍數，求出符合條件的a,b的最小差值

樣例輸入

6 36

樣例輸出

6

數據范圍限制

提示

數據說明：

對于50%的數據，1<=a<=b<=10^3。

對于100%的數據，1<=a<=b<=10^9。

解題思路：

先用最小公倍數除以最大公因數，得出a,b（已經除過最大公因數）的乘積，然后分解質因數，將相同的乘在一起，再用dfs分配到兩邊求出最小的差，最后還要乘上最大公因數

#include<cstdio> #include<iostream> 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 (xx<yy) return xx;return yy; } void dfs(long x,long y,int dep)//分配 {if (dep>w){if (x>y) ans=minn(ans,x-y);//要使差是整數else ans=minn(ans,y-x);return;}dfs(x*a[dep],y,dep+1);//分配給左邊dfs(x,y*a[dep],dep+1);//分配給右邊 } int main() {scanf("%lld %lld",&n,&m);t=m/n;num=2;while(t!=1)//沒有除完if (t%num==0) //可以整除{t/=num;//除if (o) a[w]*=num;//已經有同樣的數，就乘在一起，避免不是互質else a[++w]=num,o=1;//沒有同樣的數，自己單獨一個}else num++,o=0;//除數++ans=9223372036854775807;//long long的范圍，2^63-1dfs(1,1,1);//dfs分配printf("%lld",ans*n);//乘上最大公因數return 0; }

總結

以上是生活随笔為你收集整理的【dfs】GCD与LCM（jzoj 1608）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。