同 [类欧几里得算法 数论] BZOJ 2187 fraction
AwD orzz
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; typedef pair<ll,ll> abcd; abcd Solve(ll p1,ll q1,ll p2,ll q2) { ll l=p1/q1+1; abcd ret; if (l*q2<p2) return abcd(l,1); if (p1==0) return abcd(1,q2/p2+1); if (p1<=q1 && p2<=q2){ ret=Solve(q2,p2,q1,p1); swap(ret.first,ret.second); return ret; } ll t=p1/q1; ret=Solve(p1-q1*t,q1,p2-q2*t,q2); ret.first+=ret.second*t; return ret; } int n; ll r; int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); while (scanf("%d 0.%lld",&n,&r)==2){ if (r==0) { printf("1\n"); continue; } ll x=10; while (n--) x*=10; ll lu=r*10-5,ld=x,ru=r*10+5,rd=x,g; g=__gcd(lu,ld); lu/=g; ld/=g; g=__gcd(ru,rd); ru/=g; rd/=g; abcd ret=Solve(lu,ld,ru,rd); printf("%lld\n",min(ret.second,ld)); } return 0; }