AtCoder AGC #015 : F - Kenus the Ancient Greek

コードは軽いが考察が重い。
http://agc015.contest.atcoder.jp/tasks/agc015_f

問題

整数(X,Y)に対し、(x,y) (1≦x≦X、1≦y≦Y)を考え、その2値にユークリッドの互除法を適用したときの除算回数を考える。
これらのうち除算回数の最大値とそれを満たす(x,y)の組み合わせ数を答えよ。

解法

詳細な理由はEditorialを参照してもらうとして、以下解法のみ説明。

f(n)をフィボナッチ数列(f(0)=1,f(1)=1)とすると、除算回数がn回となる最小値は(f(n),f(n+1))である。
(f(n),f(n+1))に対し互除法を1回適用すると、大きい方の値がf(n+1)-f(n)=f(n-1)と小さい方の値を1回引いたものになることがわかる。

レベルnのよいペア(a,b)を下記の通り定義する。

• (a,b)に互除法を行うとn回除算できる。
• a,b≦f(n+2)

このような(a,b)はちょうど2n個あり、その構成法はフィボナッチ数列の生成過程でどこか1回だけf(k+1)=f(k)+2*f(k-1)と2倍の値を足しこむことである。

(a,b)に対し、(a,b+t*a)の形の組はn回除算でき、かつ元の(a,b)が異なれば互いに異なる値を取る。
よって(a,b)は高々2*n個しかないので、x=aとしたときy=b+t*a≦Yとなるtの個数を求めればよい。

int Q;
ll F[91];
ll X,Y;

vector<pair<ll,ll>> cand[91];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	F[0]=F[1]=1;
	for(i=2;i<=89;i++) {
		F[i]=F[i-1]+F[i-2];
		for(j=2;j<=i+1;j++) {
			ll a=1,b=1;
			for(x=2;x<=i;x++) {
				ll c=b+a;
				if(x==j) c+=a;
				b=a;
				a=c;
			}
			cand[i].push_back({a,a+b});
			cand[i].push_back({a+b,a});
		}
	}
	
	
	cin>>Q;
	while(Q--) {
		cin>>X>>Y;
		
		if(X>Y) swap(X,Y);
		if(X==1 || (X==2&&Y==2)) {
			cout<<1<<" "<<(X*Y)%mo<<endl;
			continue;
		}
		
		int k=0;
		while(F[k+1]<=X && F[k+2]<=Y) k++;
		ll ret=0;
		FORR(r,cand[k]) if(X>=r.first && Y>=r.second) {
			(ret += 1+(Y-r.second)/r.first)%=mo;
		}
		cout<<k<<" "<<ret<<endl;
		
	}
}

まとめ

こういうのどこから思いつくんだ。