yukicoder : No.1936 Rational Approximation

完全に考察中心の問題。
https://yukicoder.me/problems/no/1936

問題

既約分数P/Qが与えられる。
分母がQ未満の既約分数のうち、LはP/Q未満の最大値、RはP/Qより大きな最小値とする。
L,Rの分子と分母の和を求めよ。

解法

LとRの分子の和はP、分母の和はQとなり、解は(P+Q)となる。

L=Al/Bl、R=Ar/Brとする。
P/Q-L=(1/Q)*(P*Bl-Q*Al)/Blとなる。ここでP*Bl-Q*Al=1となるAl,Blは(ユークリッドの互除法を考えると)ただ一つ存在する。
同様にR-P/Qを考えると、P*Br-Q*Ar=-1となるAr,Brは(ユークリッドの互除法を考えると)ただ一つ存在する。
両式を足すとP(Bl+Br)-Q(Al+Ar)=0であり、PとQが素であることからAl+Ar=P、Bl+Br=Qとなる。

ll P,Q;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P>>Q;
	cout<<P+Q<<endl;
}

まとめ

本番結構通してる人多いな。
皆普通に導いたのか、周知の事実なのか、実験ゲーだったのか…。