JOI 2008 春合宿 day3-2 「Fraction」

ファレイ数列ですね。
エジプト→ファラオ→ファレイっていう発想だったりして・・・

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define fi first
#define se second
using namespace std;

typedef pair<int, int> P;


int m, k;


P farey(P a, P b){
	if(a.se+b.se > m) return P(0,0);
	P c = P(a.fi+b.fi, a.se+b.se);
	
	P x = farey(a, c);
	if(x.se) return x;
	
	k--;
	if(!k) return c;
	
	return farey(c, b);
}


int main(){
	scanf("%d%d",&m,&k);
	
	P ans = farey(P(0,1), P(1,1));
	
	if(ans.se) printf("%d %d\n",ans.fi, ans.se); else puts("-1");
	
	return 0;
}

そういえば、ファレイ数列をネタにして作った問題があるんですが、
0282 - Herbert Online Judge
１位の人どうやって解いたんだろう？
出題者のくせに露骨なやり方でしか解いてないという・・・