题目链接：http://codeforces.com/contest/837/problem/F

题意：已知f(a, 0) = 0， f(a, b) = 1+f(a, b-gcd(a,b))。给出x,y求f(x,y)，其中x<=1e12,y<=1e12。

解法：设x = A*gcd1, y = B*gcd1，如果A,B互质，就可以继续减去gcd1，直到y=(B-m)*gcd1，这个时候A和B-m有公因数k(m = B%k)， gcd2 = k*gcd1，k是A的质因子

则对A的所有的因子求出m，取小，就是gcd变化所需要的次数，累加到答案，并且让y减掉gcd1对应的那部分就好了。


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
set <LL> s;
void Insert(LL x){
    s.clear();
    for(LL i=2; i*i<=x; i++){
        if(x%i==0){
            s.insert(i);
            x/=i;
            while(x%i==0) x/=i;
        }
    }
    if(x>1) s.insert(x);
}

int main()
{
    LL x, y;
    while(~scanf("%lld %lld", &x, &y)){
        Insert(x);
        LL ans = 0, m;
        while(y){
            LL g = __gcd(x, y);
            x /= g, y /= g;
            m = y;
            for(auto i : s){
                if(x%i==0) m = min(m, y%i);
            }
            ans += m;
            y -= m;
        }
        printf("%lld\n", ans);
    }
    return 0;
}