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

    
            

            




            







												


        

            
	

            yuanyuelang
            

            

            


            
	
		

            常用鏈接
            

		

            統(tǒng)計(jì)
            
	
		
		

		

            最新評(píng)論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			數(shù)論(2)-------擴(kuò)展歐幾里得算法
		
            
		擴(kuò)展歐幾里得算法------求解線性方程ax+by=c

            1.應(yīng)用：
                  線性方程ax+by=c ,已知a,b,c，求解x,y.

            2.基本思路：
                 
                  ax+by=c有解 => c=k*gcd(a,b)=kd（因?yàn)閐=gcd(a,b)=>d|(ax+by))
                  
                  我們先考慮求解  ax+by=d
                    由歐幾里得算法,d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b])y'    
                    則由上述兩式子，我們可以得出 x=y' ,y=x'-[a/b]y'
                    這樣子，在歐幾里得算法添加x,y變量，最后得到解。（可結(jié)合下面代碼源代碼進(jìn)行理解）

                  接下來我們來看看ax'+by'=d和ax+by=c之間的關(guān)系
                  
                    （c/d)ax'+(c/d)by'=(c/d)d 即 可以得到 x=(c/d)x',y=(c/d)y'
                     
                     所以可以得到ax+by的一組解
                     那么ax+by=c所有解的形式是什么呢？
                         a(x+qb)+b(y-qa)=c; q為任意整數(shù)
            (注意，當(dāng)要求y-qa的最小正整數(shù)min時(shí),由y-qa>=0， q取[y/a]最小，min=y-[y/a]y,但是,[y/a]可能為0，如果y是負(fù)數(shù)，min此時(shí)也為負(fù)數(shù)，不好，此時(shí)令min+=a就可以取得最小正整數(shù)值了（[y/a]=0所以|y|<a),這段可以自己找個(gè)例子好好理解下啊）

            3.源代碼模板
            

             1int Extended_Euclid(int a,int b,int& x,int &y)
             2{
             3    if(b==0){
             4        x=1;
             5        y=0;
             6        return a;
             7    }
             8    int d=Extended_Euclid(b,a%b,x,y);
             9    int temp=x;x=y;y=temp-a/b*y;
            10    return d;
            11}
            12//用擴(kuò)展歐幾里得算法解線性方程ax+by=c;
            13bool linearEquation(int a,int b,int c,int& x,int &y)
            14{
            15    int d=Extended_Euclid(a,b,x,y);
            16    if(c%d) return false;
            17
            18    int k=c/d;
            19    x*=k;y*=k;//求的只是其中一個(gè)解
            20    return true;
            21}
            

            四.學(xué)習(xí)心得
                擴(kuò)展歐幾里得算法的妙用，值得好好體會(huì)，對(duì)整個(gè)過程自己可以找個(gè)例子好好印證一下，肯定印象深刻。去Google一下POJ上的這方面的題目好好實(shí)踐一下吧！！！            

		
            
			posted on 2009-09-05 16:51 原語餓狼 閱讀(4240) 評(píng)論(4)  編輯 收藏 引用  所屬分類: 數(shù)論 
		
            
	
            
	
	


	


            
	    
    


            

            評(píng)論
            
	
	
			
            
				# re: 數(shù)論(2)-------擴(kuò)展歐幾里得算法
					
						2011-02-02 09:34
					
				ding
			
            
			
            
				頂  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: 數(shù)論(2)-------擴(kuò)展歐幾里得算法
					
						2011-04-07 23:08
					
				曉楠
			
            
			
            
				由歐幾里得算法,d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b])y'    

            

            這句話應(yīng)該是

            d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b]y')    

              回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: 數(shù)論(2)-------擴(kuò)展歐幾里得算法
					
						2011-10-03 17:34
					
				CrazyForAC
			
            
			
            
				min=y-[y/a]y錯(cuò)了.  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: 數(shù)論(2)-------擴(kuò)展歐幾里得算法
					
						2013-12-15 20:43
					
				s
			
            
			
            
				定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不為0)  回復(fù)  更多評(píng)論
				  
			
            
		

            




            






            

				

            



    
    







            
	   
	



无码乱码观看精品久久|
久久综合88熟人妻|
久久久久亚洲av毛片大|
亚洲国产日韩欧美综合久久|
久久精品国产亚洲av麻豆图片|
久久综合九色综合网站|
久久国产V一级毛多内射|
亚洲级αV无码毛片久久精品|
久久综合久久综合久久|
亚洲精品无码久久久久去q|
国产精品视频久久久|
久久精品国产99国产精品导航|
久久婷婷国产麻豆91天堂|
日本强好片久久久久久AAA|
久久精品国产一区二区|
99精品久久精品一区二区|
综合久久久久久中文字幕亚洲国产国产综合一区首
|
久久国产精品-久久精品|
伊人久久大香线蕉AV一区二区|
99久久综合国产精品二区|
国内精品久久久久久久久电影网
|
久久国产视屏|
99麻豆久久久国产精品免费|
中文字幕乱码人妻无码久久|
亚洲午夜精品久久久久久app|
久久国产一区二区|
国内精品欧美久久精品|
少妇被又大又粗又爽毛片久久黑人
|
亚洲欧美一区二区三区久久|
久久久久香蕉视频|
久久久久国产视频电影|
久久国产香蕉一区精品|
欧美激情精品久久久久久久九九九|
国产精品天天影视久久综合网|
国产精品久久久福利|
AV无码久久久久不卡蜜桃|
久久97精品久久久久久久不卡|
狠狠色婷婷综合天天久久丁香|
狠狠色丁香婷婷综合久久来|
精品久久久久久久久久久久久久久|
亚洲欧美精品伊人久久|