首页 > 考试 > 其他 > 正文
[BZOJ2712][Violet 2][类欧几里得算法]棒球
2017-03-14 09:24:43       个评论    来源:CE玩家  
收藏    我要投稿

[BZOJ2712][Violet 2][类欧几里得算法]棒球。
把小数转化成分数,就行了。

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair pairs;

int n;
ll r,x,a,b,c,d;

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,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+=t*r.second;
    return r;
}

int main(){
    while(~scanf("%d 0.%lld",&n,&r)){
        if(r==0){ puts("1"); continue; }
        x=1; for(int i=1;i<=n+1;i++) x*=10;
        a=r*10-5; b=x; c=r*10+5; d=x;
        simplify(a,b); simplify(c,d);
        pairs Ans=solve(a,b,c,d);
        printf("%lld\n",min(Ans.second,b));
    }
}
?
点击复制链接 与好友分享!回本站首页
上一篇:[BZOJ2187][类欧几里得算法]fraction
下一篇:使用jhipster搭建微服务
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站