• <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 閱讀(306) 評論(0)  編輯 收藏 引用
            国产精品久久久久久久人人看| 久久精品aⅴ无码中文字字幕重口| 久久久噜噜噜久久熟女AA片| 亚洲欧美成人久久综合中文网| 亚洲αv久久久噜噜噜噜噜| 久久青青草原亚洲av无码app| 久久电影网一区| 久久久久久无码国产精品中文字幕| 一97日本道伊人久久综合影院| 久久国产精品无码一区二区三区| 久久久久久综合一区中文字幕| 午夜精品久久久内射近拍高清| 久久婷婷五月综合97色| 久久本道久久综合伊人| 亚洲人成网亚洲欧洲无码久久| 亚洲午夜精品久久久久久人妖| 国内高清久久久久久| www.久久热| 色综合久久天天综线观看| 99久久99这里只有免费的精品| 久久91精品国产91| 国产精品嫩草影院久久| 久久夜色精品国产网站| 久久人人超碰精品CAOPOREN | 精品久久久久久国产免费了| 日产精品久久久久久久| 久久国产精品波多野结衣AV| 久久久久高潮毛片免费全部播放| 久久婷婷色香五月综合激情| 久久国产成人午夜aⅴ影院| 婷婷综合久久狠狠色99h| 日韩av无码久久精品免费| 亚洲一级Av无码毛片久久精品| 成人午夜精品久久久久久久小说| 久久精品草草草| 99久久精品国内| 九九久久99综合一区二区| 99999久久久久久亚洲| 香蕉久久夜色精品国产小说| 狠狠色丁香婷婷久久综合不卡| 国产情侣久久久久aⅴ免费|