Codeforces ECR #026 : E. Vasya's Function

せっかくの全完チャンスを逃した。
http://codeforces.com/contest/837/problem/E

問題

関数fを以下のように定める。

• f(a,0) = 0
• f(a,b) = 1 + f(a,b-gcd(a,b)) (b＞0の場合)

2値X,Yが与えられるので、f(X,Y)を求めよ。

解法

XとYが公約数gを持つなら、f(X,Y)=f(X/g,Y/g)となるのは自明である。
よってXとYが互いに素であるケースを考える。

この時、gcd(X,Y)=1なので、基本的にf(X,Y)=1+f(X,Y-1)である。
ただしYをデクリメントしていく際、途中でXとYが2以上の公約数を持つようになると、以後のYの減り方は変化する。

そこで、Xの約数を列挙し、Yをデクリメントしていったときその約数の倍数に最初に到達するケースを求めよう。
仮にa回デクリメントすると初めてXの約数bの倍数になるとき、f(X,Y) = a + f(X/b, (Y-a)/b)となる。

ll X,Y;
vector<ll> V;

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}

ll hoge(ll X,ll Y) {
	if(Y==0) return 0;
	if(Y%X==0) return Y/X;
	ll g=__gcd(X,Y);
	X/=g;
	Y/=g;
	
	ll mi=1LL<<60;
	FORR(v,V) if(X%v==0 && v>1) mi=min(mi,Y-Y/v*v);
	return mi+hoge(X,Y-mi);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y;
	V=enumdiv(X);
	cout<<hoge(X,Y)<<endl;
	
}

まとめ

言われてみると単純なんだけどちょっと手間取った。