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

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>
            欧美经典一区二区| 欧美一区二区视频在线| 久久久久久欧美| 欧美在线一二三四区| 夜夜嗨av一区二区三区四季av| 久久久精品动漫| 国产综合网站| 国产精品一区二区你懂的| 国产精品人人做人人爽人人添| 欧美日韩三级视频| 欧美日韩国产综合视频在线观看中文| 久久亚洲二区| 欧美精品激情在线观看| 欧美巨乳在线| 国产欧美一区二区三区沐欲| 国产亚洲在线| 亚洲人成毛片在线播放女女| 亚洲欧美乱综合| 欧美3dxxxxhd| 亚洲网站在线观看| 麻豆av一区二区三区久久| 欧美日韩精品二区| 精品成人国产| 羞羞答答国产精品www一本| 久久亚洲不卡| 国产综合亚洲精品一区二| 国产精品亚洲不卡a| 国产一区二区丝袜高跟鞋图片| 国产日产亚洲精品| 一本色道久久88综合亚洲精品ⅰ| 欧美一区二区三区在线看 | 欧美一区影院| 国产亚洲欧美激情| 99国产精品| 男人的天堂成人在线| 亚洲精品一区在线观看| 欧美91大片| 亚洲黄一区二区三区| 免费观看亚洲视频大全| 久久成人这里只有精品| 欧美色一级片| 亚洲欧美日韩国产一区二区| 亚洲精品一区二区三区av| 你懂的视频一区二区| 亚洲品质自拍| 一本不卡影院| 国产日韩在线看片| 欧美风情在线| 一区二区三区日韩精品| 国产精品成人在线观看| 久久国产99| 欧美成ee人免费视频| 亚洲少妇一区| 久久综合激情| 亚洲午夜成aⅴ人片| 欧美在线你懂的| 亚洲性图久久| 在线观看91久久久久久| 亚洲欧洲日本一区二区三区| 欧美成人精品福利| 新狼窝色av性久久久久久| 久久精品日韩一区二区三区| 日韩亚洲欧美成人| 久久精品国产免费| 亚洲综合二区| 欧美日韩福利在线观看| 另类尿喷潮videofree| 欧美四级剧情无删版影片| 美女网站久久| 狠狠网亚洲精品| 性欧美长视频| 久久国产一区| 国产精品久久激情| 亚洲精品综合| 亚洲午夜激情网站| 欧美日韩精品一区二区三区| 欧美激情91| 亚洲精品资源美女情侣酒店| 久久久久久久高潮| 欧美mv日韩mv国产网站app| 国产综合网站| 免费成人激情视频| 农夫在线精品视频免费观看| 伊甸园精品99久久久久久| 久久国产精品久久久久久| 久久久午夜视频| 91久久精品国产91久久性色| 欧美精品在线看| 99国产一区| 性久久久久久久久久久久| 国产主播喷水一区二区| 久久阴道视频| 欧美二区不卡| 久久亚裔精品欧美| 亚洲欧美在线播放| 亚洲欧美中文在线视频| 国产午夜久久| 欧美激情视频一区二区三区在线播放| 亚洲区欧美区| 久久久久久亚洲精品不卡4k岛国| 韩日在线一区| 国产精品美女午夜av| 久久综合九色九九| 中文网丁香综合网| 欧美国产91| 玖玖玖国产精品| 欧美亚洲日本一区| 亚洲午夜羞羞片| 亚洲精品资源| 日韩一级精品视频在线观看| 亚洲国产一区视频| 激情欧美一区| 国产综合在线看| 国产日韩欧美精品在线| 欧美先锋影音| 国产精品美女在线观看| 国产精品扒开腿做爽爽爽视频| 久久亚洲图片| 久久伊伊香蕉| 久久一本综合频道| 欧美成人免费在线观看| 久久综合亚州| 欧美精品国产| 国产美女精品人人做人人爽| 国产欧美一区二区在线观看| 国产精品久久久久99| 国产欧美日本一区视频| 黄色小说综合网站| 99国产一区| 久久久久久久久久久久久女国产乱 | 在线成人小视频| 亚洲国产精品视频| 亚洲男人天堂2024| 欧美成人一二三| 亚洲一区二区三区高清| 久久综合给合| 国产精自产拍久久久久久蜜| 亚洲成色最大综合在线| 亚洲一区三区电影在线观看| 久久久噜噜噜久久狠狠50岁| 91久久精品美女| 久久久久久久久久久一区| 欧美日韩午夜精品| 亚洲国产婷婷香蕉久久久久久| 亚洲欧洲99久久| 日韩视频一区二区在线观看 | 亚洲精品亚洲人成人网| 久久天天狠狠| 国语自产偷拍精品视频偷| 亚洲影视中文字幕| 亚洲精品视频一区| 久久影视精品| 国产精品chinese| 亚洲精品一线二线三线无人区| 欧美日韩在线视频首页| 亚洲肉体裸体xxxx137| 久久亚洲综合色| 久久国产日韩欧美| 亚洲盗摄视频| 亚洲黄色尤物视频| 欧美片在线观看| 亚洲一区在线直播| 午夜精品久久久99热福利| 国产精品综合色区在线观看| 午夜亚洲影视| 欧美中文在线字幕| 最新国产成人av网站网址麻豆 | 欧美日一区二区在线观看| 久久在线视频在线| 一区二区三区欧美亚洲| 美女网站在线免费欧美精品| 久久综合伊人| 西西裸体人体做爰大胆久久久| 欧美一区二区福利在线| 亚洲精品日韩在线观看| 亚洲午夜影视影院在线观看| 韩国成人理伦片免费播放| 91久久国产综合久久| 国产区精品视频| 日韩小视频在线观看专区| 国产日韩欧美一二三区| 亚洲激情亚洲| 在线播放中文一区| 午夜精品三级视频福利| 亚洲视频综合| 欧美成人精品在线观看| 久热国产精品| 亚洲经典在线| 欧美主播一区二区三区| 先锋影音一区二区三区| 欧美三级免费| 亚洲香蕉网站| 久久激情视频久久| 国产伦理一区| 亚洲欧美日本国产专区一区| 亚洲午夜黄色| 国产日韩高清一区二区三区在线| 亚洲一区二区三区精品视频| 欧美亚洲日本网站| 狠色狠色综合久久|