频道栏目
首页 > 考试 > 其他 > 正文
[BZOJ2187][类欧几里得算法]fraction
2017-03-14 09:24:42      个评论    来源:CE玩家  
收藏   我要投稿

[BZOJ2187][类欧几里得算法]fraction。

题意


求p,q满足ab的解


推一发

?ab?+1≤?cd?→?ab?+1

a=0→pqdpc因为q要求最小p=1,q=?dc?

a<=bandc<=d→dc

Elsea%bb

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;
typedef pair 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\n",Ans.first,Ans.second);
    }
}
?
点击复制链接 与好友分享!回本站首页
上一篇:[BZOJ2987][类欧几里得算法]Earthquake
下一篇:[BZOJ2712][Violet 2][类欧几里得算法]棒球
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站