time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Vasya is studying number theory. He has denoted a function f(a, b) such that:
f(a, 0) = 0; f(a, b) = 1 + f(a, b - gcd(a, b)), where gcd(a, b) is the greatest common divisor of a and b. Vasya has two numbers x and y, and he wants to calculate f(x, y). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.
Input The first line contains two integer numbers x and y (1 ≤ x, y ≤ 1012).
Output Print f(x, y).
Examples input 3 5 output 3 input 6 3 output 1
题目大意：已知 f(a, 0) = 0 ， f(a, b) = 1 + f(a, b − gcd(a, b)) 给出 x,y ，求 f(x,y) 解题思路：设 x=A1gcdold,y=B1gcdold ，若 A1,B1 互质，则继续减 gcdold ，直至 y=(B1−m)gcdold ，此时 A1 和 B1−m 有公因数 k （m=B1%k）， gcdnew=k∗gcdold ， k 是A1的一个质因子，则对 A1 的所有质因数求出对应的 m ，取最小值，即为gcd变化所需的次数，根据递归式，将次数加到答案上，由上述分析可知 A1∗gcdold=A2∗k∗gcdold=A2∗gcdnew,(B1−m)gcdold=B2∗k∗gcdold=B2∗gcdnew ，故重复上述过程即可。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<set> using namespace std; typedef long long LL; const LL INF=1e18; set<LL> s; LL gcd(LL a,LL b) {return b==0?a:gcd(b,a%b);} void getfactors(LL x) { s.clear(); LL rx=sqrt(x); for(int i=2;i<=rx;i++) { if(x%i==0) { x/=i; s.insert(i); while(x%i==0) x/=i; } } if(x>1) s.insert(x); } int main() { LL x,y; while(scanf("%lld%lld",&x,&y)!=EOF) { getfactors(x); LL ans=0,m; while(y) { LL g=gcd(x,y); x/=g;y/=g; m=y; for(auto p:s) if(x%p==0) m=min(m,y%p); ans+=m; y-=m; } printf("%lld\n",ans); } return 0; } //2000000018 2000000017 //1 1000000000000 //3 135415909531