Submission #40436772

---

Source Code Expand

#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);
}

Submission Info

Judge Result