arc159b

标签：return gcd val min long x% arc159b

题目链接：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);
}

标签：return,gcd,val,min,long,x%,arc159b
From： https://www.cnblogs.com/xjwrr/p/17299783.html