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

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>
            亚洲一区精品视频| 亚洲精品欧美激情| 欧美一区二区| 国内精品写真在线观看| 久久久久九九九九| 美日韩精品视频| 亚洲精品日产精品乱码不卡| 亚洲人成在线播放| 国产精品99一区二区| 性欧美精品高清| 久久久国产精品一区| 亚洲精品在线电影| 一区二区三区久久| 黑人极品videos精品欧美裸| 欧美激情中文不卡| 国产精品久久久久久久久婷婷 | 亚洲国产成人久久综合| 亚洲高清一区二| 国产精品人人做人人爽人人添| 久久久成人网| 欧美精品黄色| 久久精品在线播放| 欧美黄色免费| 久久gogo国模裸体人体| 欧美 日韩 国产精品免费观看| 亚洲主播在线| 老司机成人网| 亚洲天堂网站在线观看视频| 欧美在线啊v| 日韩午夜三级在线| 久久精品99| 亚洲综合日韩中文字幕v在线| 久久精品一区二区三区中文字幕 | 国产精品第一区| 久久免费少妇高潮久久精品99| 欧美福利电影网| 久久嫩草精品久久久久| 欧美日韩在线免费观看| 欧美1区视频| 国产一区二区三区久久精品| av成人动漫| 亚洲精品乱码| 久久青草欧美一区二区三区| 午夜在线观看欧美| 欧美视频在线不卡| 亚洲高清毛片| 在线免费一区三区| 欧美一区二区三区精品电影| 亚洲欧美视频一区| 欧美日韩在线不卡| 亚洲欧洲日产国产综合网| 精品不卡视频| 欧美在线999| 久久精品一区二区| 国产欧美日韩中文字幕在线| 99精品欧美一区二区三区综合在线| 亚洲第一在线综合在线| 久久蜜桃精品| 毛片一区二区| 在线成人小视频| 久久久噜噜噜久久| 久久夜色精品国产亚洲aⅴ| 国产免费亚洲高清| 午夜精彩视频在线观看不卡| 亚洲欧美精品一区| 国产精品美女午夜av| 亚洲专区一区二区三区| 亚洲一区亚洲| 国产精品日韩精品| 亚洲欧美日韩在线播放| 久久av一区二区| 国产日韩欧美不卡在线| 欧美在线一级va免费观看| 久久人人爽人人爽| 亚洲第一区中文99精品| 午夜欧美精品久久久久久久| 亚洲高清免费在线| 欧美日韩精品免费看| 欧美高潮视频| 亚洲精品视频在线| 欧美日韩国产三区| 亚洲午夜久久久久久久久电影院 | 亚洲欧美国产一区二区三区| 国产精品国产a| 香蕉尹人综合在线观看| 久久久久一区二区三区| 亚洲国产成人久久综合| 欧美人成在线| 亚洲综合视频在线| 嫩模写真一区二区三区三州| 亚洲精品之草原avav久久| 欧美午夜片在线观看| 亚洲欧美日韩国产中文| 亚洲视频在线观看免费| 亚洲美女免费精品视频在线观看| 亚洲免费影视| 国产婷婷色一区二区三区| 久久久精品2019中文字幕神马| 亚洲电影av| 亚洲一区二区三区免费观看| 国产精品永久免费视频| 老牛国产精品一区的观看方式| 亚洲人成77777在线观看网| 午夜精品www| 在线视频观看日韩| 国产精品久久久久一区二区三区 | 免费永久网站黄欧美| 亚洲国产一区视频| 国产精品成人一区二区三区吃奶| 久久成人免费视频| 亚洲日韩视频| 久久亚洲影音av资源网| 这里是久久伊人| 亚洲第一黄网| 国产欧美日韩精品丝袜高跟鞋| 久久久精品视频成人| 在线视频精品一区| 欧美国产三级| 久久婷婷激情| 久久成人精品无人区| 亚洲精品中文字幕女同| 韩日精品视频| 国产毛片久久| 欧美日韩在线大尺度| 欧美成人黑人xx视频免费观看| 性做久久久久久| 在线亚洲高清视频| 99国产精品私拍| 亚洲国产精品一区二区第四页av | 久久亚洲高清| 欧美在线视频播放| 亚洲与欧洲av电影| 国产精品99久久不卡二区| 亚洲国产cao| 精品动漫av| 激情久久影院| 国内成+人亚洲| 国产亚洲制服色| 国内视频精品| 国内自拍一区| 一区二区三区无毛| 国语自产精品视频在线看8查询8 | 久久综合九色九九| 久久久噜噜噜久久中文字幕色伊伊| 亚洲综合第一| 欧美一区在线看| 久久久亚洲影院你懂的| 久久青草欧美一区二区三区| 久久男人资源视频| 免费不卡在线观看av| 美乳少妇欧美精品| 欧美日韩成人一区| 国产精品久久777777毛茸茸| 欧美四级剧情无删版影片| 欧美视频在线观看一区二区| 欧美特黄一级大片| 国产精品你懂的在线| 国产情人综合久久777777| 国产一区二区三区观看| 在线日韩欧美视频| 夜夜嗨av色一区二区不卡| 亚洲一区二区三区色| 久久成人免费网| 免费亚洲网站| 亚洲精品乱码久久久久久久久| 99亚洲精品| 欧美一区精品| 欧美精品国产一区二区| 国产精品免费看久久久香蕉| 国产日韩精品一区二区三区在线 | 日韩午夜在线电影| 亚洲欧洲av一区二区三区久久| 久久久久成人精品| 欧美激情一二三区| 中文在线资源观看网站视频免费不卡| 亚洲一区亚洲二区| 久久亚洲精品网站| 国产精品久久久久99| 精品1区2区3区4区| 亚洲天堂av电影| 裸体女人亚洲精品一区| 日韩系列在线| 久久久999国产| 国产精品久久久久9999吃药| 在线看视频不卡| 午夜精品亚洲| 亚洲国产精品成人一区二区| 先锋影音国产一区| 欧美久久婷婷综合色| 国产视频亚洲| 亚洲一区二区三区午夜| 媚黑女一区二区| 亚洲香蕉在线观看| 欧美第一黄网免费网站| 国产一区二区三区不卡在线观看 | 一区二区欧美在线| 免费亚洲电影| 欧美一区二区三区免费视| 国产精品久久久久毛片软件 | 亚洲国产第一|