青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

M.J的blog

algorithm,ACM-ICPC
隨筆 - 39, 文章 - 11, 評論 - 20, 引用 - 0
數(shù)據(jù)加載中……

TOJ 2219. A famous math puzzle

是個關(guān)于拓展歐幾里得的問題,但是很難想到。這題也是看了結(jié)題報告的~~

關(guān)于拓展歐幾里得的算法http://mj-zhang.blogbus.com/tag/拓展歐幾里得/

大意是給N個瓶子,每個瓶子有個容量C,給定一個容量W,每次只能(1)灌滿一個,(2)倒空一個,(3)把一個的水倒給另一個,直到一個滿了或者一個空了。通過三種操作,有沒有可能最后達(dá)到某個瓶子里有W的水。可以這樣考慮:

1)當(dāng)所有C都小于W,肯定不行;

2)如果有N個瓶子,N個瓶子的容量C1, C2, C3 ... Cn必然有個最大公約數(shù)P。

證明:假設(shè)n個水壺的容量分別為C1,C2,C3…..Cn.
必要性:不管執(zhí)行三種操作的那一種,壺中所含的水一定是P的整數(shù)倍.
充分性:由歐幾里德算法擴(kuò)展可知,必然存在整數(shù)A1,A2,A3…..An,使得
 A1*C1+A2*C2+A3*C3+…+An*Cn=W.
    如果Ai是正數(shù),我們就用第i個壺從水源中取Ai次水;如果Ai為負(fù)數(shù),我們就把第i個壺倒空Ai次,這樣最后必會剩下W升水

  •  1 #include<stdio.h>

     2 int gcd(int a,int b){

     3     int temp;

     4     if(a<b) {temp=b;b=a;a=temp;}

     5     if(a%b==0return b;

     6     else  return gcd(b,a%b);

     7 }
     8 int main()
     9 {
    10     int i,j,k,n,w,flag,tep,a[102];

    11     while(scanf("%d%d",&n,&w)!=EOF){

    12         if(n==0&&w==0break;

    13         flag=0;a[n+1]=0;

    14         for(i=1;i<=n;i++){

    15             scanf("%d",&a[i]);

    16             if(a[i]>=w) flag=1;

    17         }

    18         if(flag&&n!=1){

    19             tep=gcd(a[1],a[2]);

    20             for(i=3;i<=n;i++)

    21                 tep=gcd(tep,a[i]);

    22                 if(w%tep!=0)

    23                     flag=0;

    24         }

    25         if(n==1&&a[1]!=w) flag=0;

    26         else if(n==1&&a[1]==w) flag=1;

    27         if(flag) printf("YES\n");

    28         else  printf("NO\n");

    29     }
    30 
    31 }
  • posted on 2010-04-23 19:41 M.J 閱讀(252) 評論(0)  編輯 收藏 引用


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


    青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品资源在线观看| 亚洲欧美中文日韩在线| 久久国产精品一区二区| 亚洲一区中文字幕在线观看| 国产精品免费一区豆花| 先锋影音国产一区| 欧美自拍偷拍| 91久久久一线二线三线品牌| 亚洲人体1000| 欧美午夜不卡视频| 久久久天天操| 欧美激情免费观看| 午夜精品福利一区二区蜜股av| 午夜精品久久久久久久| 亚洲二区视频| 这里只有视频精品| 精品成人免费| 99视频精品全国免费| 国产在线拍偷自揄拍精品| 欧美大香线蕉线伊人久久国产精品| 欧美福利小视频| 欧美一级淫片播放口| 欧美91福利在线观看| 亚洲自拍偷拍福利| 久久资源在线| 欧美一区二区三区在线播放| 老**午夜毛片一区二区三区| 亚洲欧美在线一区| 美腿丝袜亚洲色图| 欧美在线视频免费观看| 欧美日韩成人在线视频| 老司机aⅴ在线精品导航| 欧美午夜激情在线| 亚洲第一网站| 国产主播一区二区三区| 99亚洲一区二区| 亚洲国产婷婷| 久久精品国产一区二区电影| 亚洲一级在线观看| 欧美激情亚洲精品| 美女视频黄a大片欧美| 国产精品系列在线播放| 亚洲精品在线免费| 最新国产成人av网站网址麻豆| 午夜精品久久久久久| 亚洲一区欧美激情| 欧美区在线观看| 欧美激情第一页xxx| 国产一区二区久久久| 亚洲一二三区在线| 在线视频欧美日韩精品| 欧美激情a∨在线视频播放| 久久久水蜜桃| 狠狠色综合日日| 欧美一区二区高清| 欧美在线关看| 国产日韩精品综合网站| 亚洲一区二区在线观看视频| 亚洲一级特黄| 国产精品成人一区二区艾草| 亚洲免费观看高清在线观看 | 国产精品免费视频xxxx| 欧美日韩亚洲另类| 免费成年人欧美视频| 国产日韩一区| 久久av红桃一区二区小说| 久久久精品一区| 国产性天天综合网| 久久精品国产精品亚洲| 毛片基地黄久久久久久天堂| 激情综合自拍| 欧美国产综合| 亚洲美女视频网| 欧美亚洲自偷自偷| 国语自产精品视频在线看抢先版结局 | 欧美另类99xxxxx| 亚洲精品乱码久久久久久久久| 日韩视频免费观看高清完整版| 久久久久成人精品| 亚洲电影免费| 欧美日本免费| 香港久久久电影| 免费不卡亚洲欧美| 正在播放亚洲一区| 国产欧美日韩激情| 久久香蕉国产线看观看av| 亚洲国产日韩一区| 亚洲在线中文字幕| 激情久久五月天| 欧美激情亚洲激情| 性欧美xxxx视频在线观看| 蜜桃伊人久久| 一区二区三区欧美成人| 国产午夜亚洲精品羞羞网站| 欧美成年网站| 午夜欧美精品| 亚洲国产高清一区二区三区| 亚洲免费综合| 韩国一区二区三区在线观看| 欧美巨乳在线观看| 久久成人免费| 99视频日韩| 欧美成人r级一区二区三区| 亚洲一区二区三区免费在线观看| 国产一区二区三区免费不卡 | 国产精品女主播在线观看| 巨胸喷奶水www久久久免费动漫| 日韩亚洲欧美成人| 美女视频黄 久久| 欧美一区二区精美| 一本色道久久综合狠狠躁的推荐| 国产亚洲网站| 国产精品wwwwww| 暖暖成人免费视频| 久久精品免费电影| 亚洲资源av| 亚洲精选在线| 亚洲国产导航| 欧美成人久久| 久久婷婷麻豆| 久久av在线| 午夜精品www| 亚洲免费视频在线观看| 亚洲综合色丁香婷婷六月图片| 久久久国产精品亚洲一区| 91久久久久久| 欧美黑人一区二区三区| 久久久欧美一区二区| 欧美一区三区二区在线观看| 亚洲视频欧洲视频| 99视频精品| 亚洲精品你懂的| 亚洲激情av| 亚洲国产经典视频| 伊人久久综合97精品| 国产亚洲精品资源在线26u| 国产精品一页| 国产色婷婷国产综合在线理论片a| 欧美日韩精品福利| 欧美日韩免费在线视频| 欧美日韩精品一区视频| 欧美日韩一卡二卡| 欧美性视频网站| 国产精品高清网站| 国产美女精品视频免费观看| 国产精品久久久久aaaa| 国产欧美精品va在线观看| 国产精品久久久久久久久免费桃花 | 国内精品写真在线观看| 韩国一区电影| 91久久综合| 亚洲美女在线一区| 亚洲性视频网站| 欧美一区2区三区4区公司二百| 午夜日韩福利| 久久人人爽爽爽人久久久| 你懂的视频一区二区| 最新中文字幕一区二区三区| 亚洲区一区二| 亚洲欧美激情精品一区二区| 久久精品国产999大香线蕉| 久久久久综合网| 欧美日韩第一页| 国产精品入口日韩视频大尺度| 国产欧美日韩精品专区| 亚洲第一页在线| 在线视频亚洲欧美| 久久激情视频免费观看| 欧美r片在线| 一区二区三区不卡视频在线观看| 亚洲欧美日韩国产一区二区三区| 久久精品系列| 欧美日韩一区二区三区视频 | 国产欧美一区二区色老头| 亚洲电影免费在线| 亚洲一区国产视频| 久热这里只精品99re8久| 9色国产精品| 久久亚洲私人国产精品va| 国产精品国产三级国产aⅴ入口 | 欧美在线亚洲综合一区| 亚洲国产高清一区二区三区| 午夜精品久久久久久久久久久久久 | 国产精品香蕉在线观看| 亚洲国产精品一区制服丝袜 | 亚洲欧美国产高清| 久久狠狠一本精品综合网| 欧美激情第8页| 欧美一级一区| 欧美日韩国产小视频在线观看| 国产综合欧美| 亚洲在线视频| 91久久精品日日躁夜夜躁国产| 欧美一区二区三区四区高清| 欧美精品乱人伦久久久久久| 红桃视频一区| 欧美在线亚洲一区| 亚洲小视频在线观看| 欧美久久久久久蜜桃| 亚洲高清视频一区|