• <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>

            pku 1855 Mint 求4個(gè)數(shù)的最小公倍數(shù),歐幾里得算法

            題目很長(zhǎng),就是說(shuō)用從n種硬幣中選取4種不同的硬幣堆疊起來(lái),作為桌子的四個(gè)腿,顯然,桌子的四個(gè)腿要相等。問(wèn)對(duì)于一個(gè)給定的高度h,硬幣能夠堆成的不大于h的最大高度和不小于h的最小高度分別為多少?
            應(yīng)為數(shù)據(jù)不大, n為50左右,可以用4個(gè)for循環(huán)來(lái)枚舉硬幣,假設(shè)四種硬幣為a、b、c、d,求的這四個(gè)數(shù)的最小公倍數(shù)即可,然后就用歐幾里得算法解決。
             1/*
             2Source Code
             3
             4Problem: 1855  User: yzhw 
             5Memory: 8648K  Time: 313MS 
             6Language: G++  Result: Accepted 
             7*/

             8
             9
            10# include <iostream>
            11# include <cstdio>
            12using namespace std;
            13int l[51];
            14int refer[51][51][51][51];
            15int gcd(int a,int b)
            16{
            17    while(b)
            18    {
            19        int t=a%b;
            20        a=b;
            21        b=t;
            22    }

            23    return a;
            24}

            25int main()
            26{
            27    int n,t;
            28    while(true)
            29    {
            30        scanf("%d%d",&n,&t);
            31        if(!n&&!t) break;
            32        for(int i=0;i<n;i++)
            33            scanf("%d",l+i);
            34        for(int a=0;a<n;a++)
            35                                for(int b=a+1;b<n;b++)
            36                                    //if(a!=b)
            37                                    for(int c=b+1;c<n;c++)
            38                                        //if(a!=c&&b!=c)
            39                                        for(int d=c+1;d<n;d++)
            40                                            //if(a!=d&&b!=d&&c!=d)
            41                                            {
            42                                                int lcd1=l[a]*l[b]/gcd(l[a],l[b]),lcd2=l[c]*l[d]/gcd(l[c],l[d]);
            43                                                int lcd=lcd1*lcd2/gcd(lcd1,lcd2);
            44                                                refer[a][b][c][d]=lcd;
            45
            46                                            }

            47
            48        while(t--)
            49        {
            50            int minnum=0xfffffff,maxnum=-1;
            51            int pos;
            52            scanf("%d",&pos);
            53            for(int a=0;a<n;a++)
            54                for(int b=a+1;b<n;b++)
            55                    for(int c=b+1;c<n;c++)
            56                        for(int d=c+1;d<n;d++)
            57                            {
            58
            59                                int lcd=refer[a][b][c][d];
            60                                if(pos-pos%lcd>maxnum)
            61                                    maxnum=pos-pos%lcd;
            62                                if(pos%lcd&&lcd*(pos/lcd+1)<minnum)
            63                                    minnum=lcd*(pos/lcd+1);
            64                                if(pos%lcd==0&&pos<minnum)
            65                                    minnum=pos;
            66
            67                            }

            68            printf("%d %d\n",maxnum,minnum);
            69        }

            70    }

            71    return 0;
            72}

            73
            74

            posted on 2010-10-12 23:01 yzhw 閱讀(498) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): numberic

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導(dǎo)航

            統(tǒng)計(jì)

            公告

            統(tǒng)計(jì)系統(tǒng)

            留言簿(1)

            隨筆分類(lèi)(227)

            文章分類(lèi)(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            久久精品中文字幕无码绿巨人| 亚洲精品无码久久毛片| 国产精品一区二区久久不卡| 国产精品一区二区久久精品| 精品国产综合区久久久久久| 久久亚洲国产精品成人AV秋霞| 久久久久亚洲av无码专区喷水 | 久久精品国产亚洲av瑜伽| 久久精品成人欧美大片| 影音先锋女人AV鲁色资源网久久| 热99re久久国超精品首页| 亚洲精品国产自在久久| 国产精品久久久久久搜索| 无码任你躁久久久久久老妇App| 色综合久久88色综合天天| 久久99热这里只频精品6| 99久久精品这里只有精品| 日韩人妻无码精品久久久不卡| 久久久久一级精品亚洲国产成人综合AV区| 久久免费看黄a级毛片| 久久伊人亚洲AV无码网站| 久久精品国产精品国产精品污| 久久91精品国产91| 久久夜色精品国产亚洲av| 99热都是精品久久久久久| 久久久久亚洲av无码专区导航| 久久精品国产乱子伦| 无码任你躁久久久久久| 久久国产精品国语对白| 93精91精品国产综合久久香蕉| av午夜福利一片免费看久久 | 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区| 欧美国产成人久久精品| 久久亚洲天堂| 中文字幕亚洲综合久久菠萝蜜| 久久久久久久综合日本| 激情久久久久久久久久| 亚洲午夜久久久| 久久精品国产日本波多野结衣| 五月丁香综合激情六月久久| 亚洲色大成网站www久久九 |