题目链接：https://atcoder.jp/contests/arc159/submissions/40436772
苦思冥想搞好几个小时终于给我过了哈哈哈哈。（虽然比赛的时候没调出来。。）
思路：
\(当A,B的gcd>1时，递归搜索。
当等于1时，先求出d = A-B,然后枚举d的约数，
找一个最小的余数，可以使得gcd(A-x,B-x)>1。
特殊情况，gcd(A,B)=1并且A-B=1，易得他们始终互质，答案即为他们中取小者。\)
代码：
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long x,long long y){
if (!y) return x;
return gcd(y,x%y);
}
long long dfs(long long x,long long y){
if (abs(x-y)==1) return min(x,y);
if (!x||!y) return 0;
if (x==y) return 1;
if (gcd(x,y)>1) return dfs(x/gcd(x,y)-1,y/gcd(x,y)-1)+1;
long long d = abs(x-y);
long long val = min(d,min(x,y));
for (int i=1;i<=d/i;i++){
if (d%i==0){
if (x%i==y%i&&gcd((x-x%i),(y-y%i))==i&&i>1){
val = min(val,x%i);
}
long long j = d/i;
if (x%j==y%j&&gcd((x-x%j),(y-y%j))==j&&j>1){
val = min(val,x%j);
}
}
}
return dfs(x-val,y-val)+val;
}
int main(){
long long x,y;
cin>>x>>y;
cout<<dfs(x,y);
}