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

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			EOJ 1056 線性同余方程
		
            
		
              1/*
              2EOJ 1056 線性同余方程
              3
              4
              5----問(wèn)題描述：
              6
              7形如ax≡b(mod m) 的方程，稱為線性同余方程。編寫程序求解線性同余方程（基于歐幾里德算法）。
              8
              9
             10----輸入：
             11
             12測(cè)試包含多組測(cè)試數(shù)據(jù).
             13每組測(cè)試數(shù)據(jù)只含一行,每行有三個(gè)整數(shù)a,b,m(0<a,b,m<1000000)
             14
             15
             16----輸出：
             17
             18每組測(cè)試數(shù)據(jù)只輸出一行.如果有解,則按解的大小,從小到大輸出,兩兩之間用空格分開(kāi).如果沒(méi)有解,則輸出"No Answer."(不含引號(hào)).
             19
             20
             21----樣例輸入：
             22
             2312 54 34
             244 2 4
             25
             26
             27----樣例輸出：
             28
             2913 30
             30No Answer.
             31
             32
             33----分析：
             34
             35[1]
             36擴(kuò)展歐幾里得算法：
             37
             38a * x + b * y = d                      (1)
             39d = gcd( a, b )
             40
             41由
             42
             43b * x1 + (a % b) * y1 = d
             44
             45==>
             46
             47b * x1 + (a - (a / b) * b) * y1 = d
             48
             49==>
             50
             51b * x1 + a * y1 - (a / b) * b * y1 = d
             52
             53==>
             54
             55a * y1 + b * (x1 - (a / b) * y1) = d   (2)
             56
             57
             58比較 (1) 和 (2) 得
             59
             60x = y1
             61y = x1 - (a / b) * y1
             62
             63
             64
             65[2]
             66方程 ax≡b(mod m) 
             67
             68==>
             69
             70ax + my = b
             71
             72==>
             73
             74當(dāng)且僅當(dāng) b % gcd(a, m) == 0 時(shí)有解
             75
             76
             77*/
             78
             79
             80#include <iostream>
             81#include <cstdio>
             82#include <algorithm>
             83
             84using namespace std;
             85
             86#define  N  1000009
             87
             88typedef __int64 Lint;
             89
             90int gcd( int a, int b ) {
             91        int t;
             92        while ( 0 != b ) {
             93                t = a;
             94                a = b;
             95                b = t % b;
             96        }
             97        return a;
             98}
             99
            100int gcd_ex( int a, int b, int &x, int &y ) {
            101        if ( b == 0 ) {
            102                x = 1;
            103                y = 0;
            104                return a;
            105        }
            106        int d = gcd_ex( b, a % b, x, y );
            107        int t = x;
            108        x = y;
            109        y = (int)(t - ( a / b ) * ((Lint)(y)));
            110        return d;
            111}
            112
            113int a, b, m;
            114
            115int n, x[ N ];
            116
            117int solve() {
            118        int i, d, tx, ty;
            119        Lint tmp;
            120        d = gcd( a, m );
            121        if ( b % d != 0 ) {
            122                return 0;
            123        }
            124        gcd_ex( a / d, m / d, tx, ty );
            125        tx *= b / d;
            126        n = d;
            127        for ( i = 0; i < n; ++i ) {
            128                tmp = tx + m / d * ((Lint)(i));
            129                if ( 0 > tmp ) {
            130                        x[ i ] = m - ( (-tmp) % m );
            131                }
            132                else {
            133                        x[ i ] = tmp % m;
            134                }
            135        }
            136        sort( x, x + n );
            137        return 1;
            138}
            139
            140int main() {
            141        int i;
            142        while ( scanf( "%d%d%d", &a, &b, &m ) == 3 ) {
            143                if ( solve() ) {
            144                        printf( "%d", x[ 0 ] );
            145                        for ( i = 1; i < n; ++i ) {
            146                                printf( " %d", x[ i ] );
            147                        }
            148                        printf( "\n" );
            149                }
            150                else {
            151                        puts( "No Answer." );
            152                }
            153        }
            154        return 0;
            155}
            156
            
		
            
			posted on 2012-06-01 21:26 coreBugZJ 閱讀(778) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、Mathematics 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



怡红院日本一道日本久久|
国产精品久久波多野结衣|
一本色道久久HEZYO无码|
少妇久久久久久被弄到高潮|
91精品日韩人妻无码久久不卡|
 久久综合九色综合久99|
国内精品久久久久久久coent
|
亚洲va中文字幕无码久久不卡|
久久婷婷五月综合97色|
精品久久国产一区二区三区香蕉|
日韩AV毛片精品久久久|
伊人久久久AV老熟妇色|
久久精品国产亚洲沈樵|
人妻无码中文久久久久专区|
国产∨亚洲V天堂无码久久久|
久久午夜无码鲁丝片秋霞
|
亚洲七七久久精品中文国产|
久久美女网站免费|
久久精品无码午夜福利理论片|
久久久久久亚洲精品不卡|
99久久人人爽亚洲精品美女|
久久久久久精品无码人妻|
日韩欧美亚洲综合久久影院Ds|
久久久久免费看成人影片|
女人高潮久久久叫人喷水|
亚洲精品国产成人99久久|
999久久久免费精品国产|
伊人久久大香线焦AV综合影院
|
久久综合偷偷噜噜噜色|
国产精品久久久久乳精品爆|
久久精品国产免费一区|
久久男人Av资源网站无码软件|
久久精品国产亚洲αv忘忧草
|
精品多毛少妇人妻AV免费久久|
久久综合久久综合九色|
久久精品国产亚洲AV电影|
亚洲AV无码久久寂寞少妇|
777午夜精品久久av蜜臀
|
精品无码久久久久久午夜|
亚洲色欲久久久综合网东京热|
大香伊人久久精品一区二区|