• <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 1117 剩余定理
		
            
		
              1/*
              2EOJ 1117 剩余定理
              3
              4
              5----問題描述：
              6
              7求正整數(shù)中滿足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … 的最小解。a[i]是一些兩兩互質(zhì)的正整數(shù)。
              8
              9
             10----輸入：
             11
             12輸入數(shù)據(jù)的第一行為一個(gè)正整數(shù)T，表示有T組測(cè)試數(shù)據(jù)。
             13每組測(cè)試數(shù)據(jù)的第一行為一個(gè)正整數(shù)M，表示數(shù)組a和b中各有M個(gè)元素。0<M<=1000
             14接下來(lái)兩行，每行各有M個(gè)正整數(shù)，分別為a和b中的元素。
             15
             16
             17----輸出：
             18
             19每組輸出占一行，輸出滿足方程組的最小正解X.
             20
             21
             22----樣例輸入：
             23
             242
             252
             262 3
             270 1
             283
             293 5 7
             302 3 2
             31
             32
             33----樣例輸出：
             34
             354
             3623
             37
             38
             39----分析：
             40
             41中國(guó)剩余定理。
             42
             43
             44*/
             45
             46
             47#include <iostream>
             48#include <cstdio>
             49
             50using namespace std;
             51
             52typedef  __int64  Lint;
             53
             54template< class T >
             55T gcd( T a, T b ) {
             56        T t;
             57        while ( 0 != b ) {
             58                t = a;
             59                a = b;
             60                b = t % b;
             61        }
             62        return a;
             63}
             64
             65template< class T, class LT >
             66T gcd_ex( T a, T b, LT &x, LT &y ) {
             67        if ( b == 0 ) {
             68                x = 1;
             69                y = 0;
             70                return a;
             71        }
             72        T d = gcd_ex( b, a % b, x, y );
             73        LT t = x;
             74        x = y;
             75        y = t - ( a / b ) * y;
             76        return d;
             77}
             78
             79// ax = 1 (mod m)
             80// calc x
             81template< class T >
             82T axm( T a, T m ) {
             83        T x, y;
             84        if ( 1 == gcd_ex( a, m, x, y ) ) {
             85                return x;
             86        }
             87        return 0;
             88}
             89
             90#define  K  1009
             91int k;
             92int m[ K ], b[ K ];
             93
             94Lint solve() {
             95        Lint MM = 1, M[ K ], x = 0;
             96        int i;
             97        for ( i = 0; i < k; ++i ) {
             98                MM *= m[ i ];
             99        }
            100        for ( i = 0; i < k; ++i ) {
            101                M[ i ] = MM / m[ i ];
            102        }
            103        for ( i = 0; i < k; ++i ) {
            104                x += axm( M[ i ], (Lint)m[ i ] ) * M[ i ] * b[ i ];
            105                if ( 0 > x ) {
            106                        x = MM - (-x) % MM;
            107                }
            108                else {
            109                        x = x % MM;
            110                }
            111        }
            112        return x;
            113}
            114
            115int main() {
            116        int tc, i;
            117        scanf( "%d", &tc );
            118        while ( 0 < tc-- ) {
            119                scanf( "%d", &k );
            120                for ( i = 0; i < k; ++i ) {
            121                        scanf( "%d", m+i );
            122                }
            123                for ( i = 0; i < k; ++i ) {
            124                        scanf( "%d", b+i );
            125                }
            126                printf( "%I64d\n", solve() );
            127        }
            128        return 0;
            129}
            130
            
		
            
			posted on 2012-06-01 21:27 coreBugZJ 閱讀(689) 評(píng)論(0)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、Mathematics 、課內(nèi)作業(yè) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久综合九色综合97_久久久|
无码人妻少妇久久中文字幕蜜桃|
99久久精品国产高清一区二区
|
激情五月综合综合久久69|
国产亚洲色婷婷久久99精品91|
久久久国产精华液|
亚洲精品乱码久久久久久蜜桃不卡
|
国产成人无码久久久精品一|
国产韩国精品一区二区三区久久|
久久精品国产一区二区电影|
久久国产色av免费看|
91精品国产综合久久四虎久久无码一级|
久久久久久国产精品美女
|
国产欧美久久久精品|
伊人色综合久久天天人守人婷|
久久精品国产亚洲AV无码麻豆
|
香港aa三级久久三级老师2021国产三级精品三级在
|
久久精品亚洲欧美日韩久久|
亚洲AV无码成人网站久久精品大|
精品一区二区久久久久久久网站|
日日狠狠久久偷偷色综合0|
国产午夜精品久久久久免费视
|
四虎影视久久久免费观看|
AAA级久久久精品无码片|
国产精品久久婷婷六月丁香|
一本伊大人香蕉久久网手机|
国产成人精品综合久久久久|
久久夜色精品国产www|
岛国搬运www久久|
亚洲乱亚洲乱淫久久|
日韩久久久久久中文人妻|
久久只这里是精品66|
中文字幕精品久久|
少妇被又大又粗又爽毛片久久黑人|
国产亚洲欧美成人久久片|
国产精品久久久久久一区二区三区
|
日本久久中文字幕|
看全色黄大色大片免费久久久|
99久久国产热无码精品免费久久久久|
久久久久亚洲av无码专区|
国内精品久久人妻互换|