• <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)  編輯 收藏 引用
            久久96国产精品久久久| 久久精品蜜芽亚洲国产AV| 99久久免费国产精精品| 色成年激情久久综合| 一本久久精品一区二区| 伊人久久大香线蕉AV色婷婷色| 日韩乱码人妻无码中文字幕久久 | 亚洲午夜久久久影院伊人| 日韩久久久久久中文人妻| 品成人欧美大片久久国产欧美...| 亚洲国产成人久久一区久久| 亚洲级αV无码毛片久久精品 | 亚洲国产成人久久一区久久 | 亚洲国产天堂久久综合| 一级做a爰片久久毛片看看| 日韩精品久久无码中文字幕| 久久r热这里有精品视频| 久久久久亚洲av综合波多野结衣 | 久久久久黑人强伦姧人妻| 久久精品国产亚洲77777| 久久久久久国产精品免费免费| 国产毛片欧美毛片久久久| 久久国产一片免费观看| 久久精品www人人爽人人| 深夜久久AAAAA级毛片免费看| 欧美日韩中文字幕久久伊人| 国内精品伊人久久久久777| 久久www免费人成看国产片| 国产免费久久久久久无码| 久久久久久久人妻无码中文字幕爆 | 亚洲国产精品18久久久久久| 亚洲精品NV久久久久久久久久| 久久国产精品-久久精品| 国产成年无码久久久久毛片| 国产情侣久久久久aⅴ免费| 中文字幕久久久久人妻| 亚洲人成网站999久久久综合| 欧美日韩中文字幕久久久不卡 | 国内精品免费久久影院| 91亚洲国产成人久久精品| 欧美日韩精品久久久免费观看|