Educational Codeforces Round 26 E. Vasya's Function(수론)

전송문: 링크 열기 클릭
E. Vasya's Function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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

제목은... 입니다.
두 개의 귀속, 만약 단순히 데이터를 뛴다면 3조의 예시를 모두 넘길 수 없으니, 나에게 왜 그런지 묻지 마라.그래서 최적화를 선택하면 F의 계산에서 매번의 귀속이 gcd(a, b)와 관련된다는 것을 알 수 있다. 그러면 a, b를 가장 간단하고 무엇이 가장 간단한 형식인지, 바로 상호질이지, 이것은 어려운 과정이다.a의 인자를 일일이 열거하여 b에서 a와 같은 인자를 모두 제거한 다음에 우연히 있는 수의 최소값을 취하는 것은 매우 번거로워 보이지만 사실은 b%a의 인자만 min을 취하면 된다.만약 a가 아무런 인자가 없다면, 즉 a가 질수일 때 순환을 끝내고, 이때 tempb와 b%a의 최소값을 다시 한 번 취해야 한다. 그렇지 않으면 14조의 데이터가 지나갈 수 없으니, 나에게 왜 그런지 묻지 마라.마지막 운행 시간 30ms, 괜찮아요.모든 데이터는 롱롱을 사용하는 것이 가장 좋다.
코드 구현:

#include
#include
#include
#define ll long long

using namespace std;

ll gcd(ll x,ll y)
{
	if(x==0)
	return y;
	
	return gcd(y%x,x);
}

ll find(ll x,ll y)
{
	if(y==0)
	return 0;
	
	ll temp=gcd(x,y);
	x/=temp;y/=temp;
	ll tempa=x,tempb=y;
	
	for(ll i=2;i*i<=x;i++)
	{
		if(x%i)
		continue;
		
		tempb=min(tempb,y%i);
		while(x%i==0)
		x/=i;
	}
	
	if(x!=1)
	tempb=min(tempb,y%x);
	
	return find(tempa,y-tempb)+tempb;
}

int main()
{
	ll a,b;
	while(cin>>a>>b)
	{
		ll sum=find(a,b);
		cout<