• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 16,comments - 0,trackbacks - 0

            # include <stdio.h>

            typedef long long int LL;

            /***************************************/
            LL Min(LL x, LL y)
            {
            ??????????????? return x < y ? x : y;
            }
            LL Max(LL x, LL y)
            {
            ??????????????? return x > y ? x : y;
            }
            LL gcd(LL x, LL y)
            {
            ??????????????? if (!y) return x;
            ??????????????? return gcd(y, x%y);
            }
            LL ex_gcd(LL a,LL b,LL &x,LL &y)
            {
            ??????????????? if(b==0)
            ??????????????? {
            ??????????????????????????????? x=1;
            ??????????????????????????????? y=0;
            ??????????????????????????????? return a;
            ??????????????? }
            ??????????????? LL g,t;
            ??????????????? g=ex_gcd(b,a%b,x,y);
            ??????????????? t=x;
            ??????????????? x=y;
            ??????????????? y=t-a/b*y;
            ??????????????? return g;
            }
            LL niyuan(LL b,LL p)
            {
            ??????????????? LL x,y;
            ??????????????? ex_gcd(b,p,x,y);
            ??????????????? return x=(x%p+p)%p;
            }
            /***************************************/
            struct frac
            {
            ??????????????? LL n, d;
            } ;
            LL A, B, C, D;
            LL LLabs(LL x)
            {
            ??????????????? return x>0 ? x:-x;
            }
            void slim(frac &x)
            {
            ??????????????? LL tmp = LLabs(gcd(x.d, x.n));
            ??????????????? x.d /= tmp;
            ??????????????? x.n /= tmp;
            }
            frac dif(frac x, frac y)
            {
            ??????????????? frac z;
            ??????????????? z.d = x.d * y.d;
            ??????????????? z.n = LLabs(x.n*y.d-x.d*y.n);
            ??????????????? slim(z);
            ??????????????? return z;
            }
            int cmp(frac x, frac y)
            {
            ??????????????? return x.n*y.d - x.d*y.n>0 ? 1:0;
            }
            frac cal(frac x, frac y, frac BA)
            {
            ??????????????? return cmp(dif(x, BA), dif(y, BA)) ? y:x;
            }
            void solve(void)
            {
            ??????????????? frac BA;
            ??????????????? BA.n = A, BA.d = B;
            ??????????????? LL n1 = niyuan(B, A);
            ??????????????? if (n1 == 0) n1 = A;
            ??????????????? LL d1 = (B*n1-1) / A;
            ??????????????? LL d2 = niyuan(A, B);
            ??????????????? if (d2 == 0) d2 = B;
            ??????????????? LL n2 = (A*d2-1) / B;
            ??????????????? frac a, b;
            ??????????????? a.n = n1, a.d = d1;
            ??????????????? b.n = n2, b.d = d2;
            ??????????????? slim(a), slim(b);
            ??????????????? frac ans = cal(a, b, BA);
            ??????????????? printf("%lld/%lld\n", ans.n, ans.d);
            }
            /***************************************/
            int main()
            {
            ??????????????? freopen("in.txt", "r", stdin);

            ??????????????? int T;
            ??????????????? scanf("%d", &T);
            ??????????????? while (T--)
            ??????????????? {
            ??????????????????????????????? scanf("%lld/%lld", &A, &B);
            ??????????????????????????????? LL tmp = gcd(A, B);
            ??????????????????????????????? if (tmp != 1)
            ??????????????????????????????? {
            ??????????????????????????????????????????????? printf("%lld/%lld\n", A/tmp, B/tmp);
            ??????????????????????????????? }
            ??????????????????????????????? else solve();
            ??????????????? }

            ??????????????? return 0;
            }

            Bert is a programmer with a real fear of floating point arithmetic. Bert has quite successfully used rational numbers to write his programs but he does not like it when the denominator grows large.

            Your task is to help Bert by writing a program that decreases the denominator of a rational number, whilst introducing the smallest error possible. For a rational number A/B, where B > 2 and 0 < A < B, your program needs to identify a rational number C/D such that:

            1. 0 < C < D < B, and
            2. the error | A/B - C/D| is the minimum over all possible values of C and D, and
            3. D is the smallest such positive integer.

            Input

            The input starts with an integer K ( 1$ \le$K$ \le$1000) that represents the number of cases on a line by itself. Each of the following K lines describes one of the cases and consists of a fraction formatted as two integers, A and B, separated by `/' such that:

            1. B is a 32 bit integer strictly greater than 2, and
            2. 0 < A < B

            Output

            For each case, the output consists of a fraction on a line by itself. The fraction should be formatted as two integers separated by `/'.

            Sample Input

            3
            1/4
            2/3
            13/21
            

            Sample Output

            1/3
            1/2
            8/13
            
            posted on 2012-09-15 17:26 yajunw 閱讀(309) 評論(0)  編輯 收藏 引用
            久久99精品国产一区二区三区| 久久香蕉一级毛片| 久久精品国产亚洲Aⅴ蜜臀色欲| 国产AV影片久久久久久| 亚洲国产日韩欧美综合久久| 亚洲AV无一区二区三区久久| 久久久综合九色合综国产| 伊人色综合久久| 中文无码久久精品| 精品免费久久久久国产一区| 狠狠色丁香久久婷婷综合蜜芽五月| 7777久久亚洲中文字幕| 日韩欧美亚洲综合久久影院Ds | 国产精品久久自在自线观看| 国产精自产拍久久久久久蜜| 久久久精品人妻一区二区三区蜜桃| 中文字幕成人精品久久不卡| 亚洲AV无码久久精品蜜桃| 久久人人爽人人爽人人片AV东京热| 久久99国产综合精品| 亚洲午夜无码久久久久小说 | 久久久久亚洲AV成人网人人软件| 久久久久人妻一区精品性色av| 久久影视综合亚洲| 99久久无码一区人妻| 久久久久久狠狠丁香| 国产V综合V亚洲欧美久久| 久久精品国产亚洲av麻豆图片| 亚洲精品tv久久久久久久久久| 国产巨作麻豆欧美亚洲综合久久| 久久久久夜夜夜精品国产| 精品久久久久久中文字幕人妻最新| 久久天天躁狠狠躁夜夜躁2014| 免费精品久久久久久中文字幕| 精品久久久久久无码中文字幕| 91精品国产高清久久久久久91| 中文字幕亚洲综合久久2| 久久久91精品国产一区二区三区| 久久精品www人人爽人人| 国内精品久久久久伊人av | 青青热久久国产久精品 |