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

M.J的blog

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

TOJ 2219. A famous math puzzle

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

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

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

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

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

證明:假設n個水壺的容量分別為C1,C2,C3…..Cn.
必要性:不管執行三種操作的那一種,壺中所含的水一定是P的整數倍.
充分性:由歐幾里德算法擴展可知,必然存在整數A1,A2,A3…..An,使得
 A1*C1+A2*C2+A3*C3+…+An*Cn=W.
    如果Ai是正數,我們就用第i個壺從水源中取Ai次水;如果Ai為負數,我們就把第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 閱讀(254) 評論(0)  編輯 收藏 引用


    只有注冊用戶登錄后才能發表評論。
    網站導航: 博客園   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精品麻豆| 一区二区三区日韩精品视频| 欧美一级在线视频| 精品1区2区3区4区| 欧美成人四级电影| 欧美福利一区二区| 亚洲视频免费| 性欧美video另类hd性玩具| 狠狠色丁香婷婷综合影院| 久久一区视频| 欧美黄色日本| 性18欧美另类| 麻豆成人综合网| 亚洲视频大全| 欧美专区18| 亚洲精品欧美专区| 亚洲影院在线| 亚洲日本无吗高清不卡| 亚洲视频一二区| 亚洲丁香婷深爱综合| 99视频在线精品国自产拍免费观看 | 亚洲午夜av在线| 午夜精品亚洲| 99re热这里只有精品视频| 亚洲欧美另类久久久精品2019| 黄色日韩网站| 亚洲一级黄色av| 亚洲国产午夜| 亚洲欧美资源在线| 亚洲精品资源美女情侣酒店| 亚洲欧美视频一区二区三区| 1024亚洲| 亚洲女人av| 亚洲小视频在线| 欧美jizz19性欧美| 久久久www成人免费精品| 欧美久久久久久久| 欧美成人一区二区三区| 国产日韩欧美成人| 一本久久青青| 亚洲美女黄色| 久久最新视频| 久久一区二区三区av| 国产精品高潮呻吟久久av无限 | 午夜精品久久久久久99热软件| 久久久久久69| 久久精品99国产精品| 国产精品久久久久久久午夜片| 欧美激情偷拍| 亚洲国产成人精品久久| 欧美亚洲日本网站| 欧美一区二区三区的| 欧美性视频网站| 亚洲精品国久久99热| 亚洲高清激情| 另类综合日韩欧美亚洲| 久久综合综合久久综合| 国产亚洲精品自拍| 欧美中文字幕视频| 久久婷婷av| 激情小说亚洲一区| 久久久噜噜噜久久中文字幕色伊伊 | 久久国内精品自在自线400部| 国产精品99一区二区| 日韩亚洲不卡在线| 一区二区三区四区五区在线| 欧美久久久久久| 日韩午夜免费视频| 亚洲欧美日韩精品久久| 国产精品福利av| 亚洲欧美成人精品| 久久国产乱子精品免费女| 国产一区二区三区高清| 久久久久久国产精品一区| 免费观看成人| 亚洲看片一区| 国产精品免费小视频| 亚洲欧美日韩国产综合精品二区| 欧美一区二区黄| 激情文学一区| 欧美精品v日韩精品v国产精品| 亚洲啪啪91| 亚洲欧美中文在线视频| 国产情侣一区| 另类尿喷潮videofree| 亚洲啪啪91| 欧美一区二区三区婷婷月色| 狠狠色狠狠色综合日日小说| 裸体歌舞表演一区二区| 日韩午夜在线观看视频| 久久精品国产96久久久香蕉| 黄色成人在线| 欧美日韩精品在线视频| 亚洲欧洲av一区二区| 欧美成人精品不卡视频在线观看| 一本色道久久加勒比88综合| 国产精品视频免费观看| 久久艳片www.17c.com| 日韩午夜剧场| 久久中文欧美| 在线一区亚洲| 尤物在线观看一区| 国产精品男gay被猛男狂揉视频| 欧美呦呦网站| 在线视频欧美一区| 亚洲二区精品| 久久久一区二区| 亚洲综合导航| 亚洲人成在线播放网站岛国| 国产精品午夜国产小视频| 欧美~级网站不卡| 欧美一区2区三区4区公司二百| 亚洲人成人99网站| 麻豆乱码国产一区二区三区| 亚洲在线免费视频| 亚洲经典一区| 依依成人综合视频| 国产乱码精品一区二区三| 欧美精品粉嫩高潮一区二区 | 另类人畜视频在线| 羞羞答答国产精品www一本| 91久久精品日日躁夜夜躁欧美 | 亚洲国产91色在线| 久久久久综合网| 性欧美超级视频| 中文久久乱码一区二区| 91久久精品美女| 伊人春色精品| 狠狠色综合网| 国产亚洲高清视频| 国产乱码精品一区二区三区av| 欧美美女bbbb| 欧美日韩免费观看一区=区三区| 久久亚洲风情| 美国十次了思思久久精品导航| 欧美在线免费观看视频| 亚洲欧美三级在线| 午夜欧美精品| 欧美一区二区三区视频| 亚洲制服av| 亚洲欧美精品在线| 新片速递亚洲合集欧美合集| 亚洲欧美日韩久久精品| 亚洲欧美福利一区二区| 午夜久久影院| 久久久久久久久久久一区| 久久黄色网页| 美女图片一区二区| 欧美激情一区二区三区高清视频 | 国产精品久久久久久久久久久久| 欧美日韩亚洲一区| 国产精品国内视频| 国产精品一区视频网站| 国产日韩欧美不卡| 在线观看欧美亚洲| 亚洲精选成人| 香蕉久久久久久久av网站| 欧美有码在线观看视频| 久久精品一区四区| 欧美gay视频| 亚洲精品资源| 香蕉乱码成人久久天堂爱免费| 欧美在线免费一级片| 麻豆国产精品一区二区三区 | 欧美日韩国产成人精品| 欧美视频成人| 国产在线观看一区| 亚洲人体偷拍| 亚洲男人影院| 欧美成人精品1314www| 亚洲美女色禁图| 午夜精品网站| 欧美成人精品一区| 国产麻豆午夜三级精品| 亚洲激情影视| 久久er99精品| 亚洲高清av| 亚洲欧美综合网| 欧美精品久久久久久久免费观看 | 国产精品久久影院| 欲色影视综合吧| 亚洲欧美国产va在线影院| 久久亚洲影院| 一区二区欧美视频| 久久人人爽人人爽爽久久| 欧美色综合天天久久综合精品| 国产午夜亚洲精品羞羞网站| 亚洲精品视频一区| 久久久水蜜桃av免费网站| 99国内精品久久久久久久软件| 久久国产视频网| 国产精品国产精品| 亚洲国产人成综合网站| 欧美专区在线观看| 日韩一级成人av| 欧美成人午夜免费视在线看片| 国产欧美视频在线观看| 亚洲一区二区三区777| 欧美激情视频网站| 久久免费精品视频|