bzoj2712 -- 类欧几里得算法类欧几里得

与bzoj2187类似，不过是要先将小数转化成四舍五入前的分数代码：

文章图片

文章图片

1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 #define ll long long 7 struct Node{ 8ll x,y; 9Node(){} 10Node(ll x,ll y):x(x),y(y){} 11 }a,b,c; 12 int n; 13 ll g,i,j,k,m,x,p; 14 inline ll _Min(ll x,ll y){return x=1){ 23int x=a.x/a.y; 24Node c=Solve(Node(a.x%a.y,a.y),Node(b.x-x*b.y,b.y)); 25return Node(c.x+x*c.y,c.y); 26} 27if(b.x>b.y)return Node(1,1); 28Node c=Solve(Node(b.y,b.x),Node(a.y,a.x)); 29return Node(c.y,c.x); 30 } 31 int main() 32 { 33while(scanf("%d 0.%lld",&n,&x)!=EOF){ 34if(x==0){printf("1\n"); continue; } 35for(p=1; n>=0; n--)p*=10; 36a=Node(x*10-5,p); b=Node(x*10+5,p); 37g=Gcd(a.x,a.y); a.x/=g; a.y/=g; 38g=Gcd(b.x,b.y); b.x/=g; b.y/=g; 39c=Solve(a,b); 40printf("%lld\n",_Min(c.y,a.y)); 41} 42return 0; 43 }

bzoj2721 【bzoj2712 -- 类欧几里得算法】