bzoj2187 -- 类欧几里得算法

2018-06-17 23:06:44来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

用类欧不断缩小规模,就能在O(T*log2n)时间内求出答案。

题解:http://blog.csdn.net/coldef/article/details/62035919

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 #define ll long long
 6 struct Node{
 7     ll x,y;
 8     Node(){}
 9     Node(ll x,ll y):x(x),y(y){}
10 }a,b,c;
11 ll g,i,j,k,n,m;
12 inline ll Gcd(ll x,ll y){return y==0?x:Gcd(y,x%y);}
13 inline ll F(ll x,ll y){return (x-1)/y+1;}
14 inline Node Solve(Node a,Node b){
15     g=Gcd(a.x,a.y);a.x/=g;a.y/=g;
16     g=Gcd(b.x,b.y);b.x/=g;b.y/=g;
17     if(a.x==0)return Node(1,b.y/b.x+1);
18     if(a.x/a.y+2<=F(b.x,b.y))return Node(a.x/a.y+1,1);
19     if(a.x/a.y>=1){
20         int x=a.x/a.y;
21         Node c=Solve(Node(a.x%a.y,a.y),Node(b.x-x*b.y,b.y));
22         return Node(c.x+x*c.y,c.y);
23     }
24     if(b.x>b.y)return Node(1,1);
25     Node c=Solve(Node(b.y,b.x),Node(a.y,a.x));
26     return Node(c.y,c.x);
27 }
28 int main()
29 {
30     while(scanf("%lld%lld%lld%lld",&a.x,&a.y,&b.x,&b.y)!=EOF){
31         g=Gcd(a.x,a.y);a.x/=g;a.y/=g;
32         g=Gcd(b.x,b.y);b.x/=g;b.y/=g;
33         c=Solve(a,b);
34         printf("%lld/%lld\n",c.x,c.y);
35     }
36     return 0;
37 }
bzoj2187

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:10:大整数加法

下一篇:类中的同名函数关系,重载,覆盖/重写,隐藏