[BZOJ 187][クラスユークリッドアルゴリズム]fraction
2416 ワード
に言及
pを求めて、qはab1発押す
⌊ab⌋+1≦⌈cd⌉−1→⌊ab⌋+1
a=0→pqdpc
q要求が最小なので
p=1,q=⌈dc⌉
a<=b and c<=d→dcElse a%bb
pを求めて、qはab
⌊ab⌋+1≦⌈cd⌉−1→⌊ab⌋+1
a=0→pq
q要求が最小なので
p=1,q=⌈dc⌉
a<=b and c<=d→dc
#include pairs;
ll a,b,c,d,g;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
inline void simplify(ll &a,ll &b){
ll g=gcd(a,b); a/=g; b/=g;
}
pairs solve(ll p1,ll q1,ll p2,ll q2){
simplify(p1,q1); simplify(p2,q2);
ll a=p1/q1+1,b=(ll)ceil((double)p2/q2)-1;
if(a<=b) return pairs(a,1);
if(p1==0) return pairs(1,(ll)(q2/p2)+1);
if(p1<=q1&&p2<=q2){
pairs r=solve(q2,p2,q1,p1);
swap(r.first,r.second);
return r;
}
ll t=p1/q1;
pairs r=solve(p1%q1,q1,p2-t*q2,q2);
r.first+=r.second*t;
return r;
}
int main(){
while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)){
pairs Ans=solve(a,b,c,d);
printf("%lld/%lld
",Ans.first,Ans.second);
}
}