• <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)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            精品午夜久久福利大片| av无码久久久久久不卡网站| 99久久www免费人成精品| 久久国产影院| 三级三级久久三级久久| 久久精品国产亚洲αv忘忧草 | 久久精品无码一区二区三区日韩| 久久久久久国产精品免费免费| 亚洲愉拍99热成人精品热久久| 国产福利电影一区二区三区久久老子无码午夜伦不 | 婷婷久久综合九色综合绿巨人| 久久久婷婷五月亚洲97号色| 久久久久18| 久久国产高潮流白浆免费观看| 狠狠色伊人久久精品综合网| 久久国产精品成人免费| 久久伊人精品青青草原日本| 国内精品久久久久国产盗摄| 无码AV波多野结衣久久| 国内精品伊人久久久影院| 久久精品黄AA片一区二区三区| 午夜精品久久久久久影视777| 久久久噜噜噜久久熟女AA片| 亚洲国产精品成人AV无码久久综合影院| 国产精品成人无码久久久久久 | 免费国产99久久久香蕉| 国产精品久久影院| 国产精品久久久久影院嫩草 | 伊人久久综合热线大杳蕉下载| 亚洲精品无码久久千人斩| 久久久久免费视频| 久久久久无码中| 精品久久久久久久久久久久久久久 | 久久笫一福利免费导航| 欧美久久综合九色综合| 国产高潮国产高潮久久久91| 伊人久久大香线蕉影院95| 99久久成人18免费网站| 国产精品无码久久四虎| 99久久精品国产一区二区三区| 亚洲成色999久久网站|