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

coreBugZJ

此 blog 已棄。

EOJ 1117 剩余定理

  1/*
  2EOJ 1117 剩余定理
  3
  4
  5----問題描述:
  6
  7求正整數中滿足: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]是一些兩兩互質的正整數。
  8
  9
 10----輸入:
 11
 12輸入數據的第一行為一個正整數T,表示有T組測試數據。
 13每組測試數據的第一行為一個正整數M,表示數組a和b中各有M個元素。0<M<=1000
 14接下來兩行,每行各有M個正整數,分別為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中國剩余定理。
 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 閱讀(707) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithmMathematics課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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| 国模私拍一区二区三区| 欧美高清视频一区二区| 欧美午夜片在线观看| 久久露脸国产精品| 欧美视频在线一区| 免费人成精品欧美精品| 欧美午夜电影完整版| 久久久久一区二区三区| 欧美久久久久久久久久| 久久久97精品| 欧美日韩亚洲91| 老司机午夜精品视频在线观看| 欧美人与性动交cc0o| 麻豆91精品| 国产精品久久久久久亚洲毛片| 久久久99精品免费观看不卡| 亚洲视频在线观看一区| 亚洲精品日韩激情在线电影| 国产在线麻豆精品观看| 亚洲精品乱码久久久久久蜜桃麻豆 | 一本色道久久综合一区| 好吊妞**欧美| 亚洲一区二区三区高清不卡| 亚洲美女91| 久久久国产精品一区二区中文| 一区二区三区视频观看| 欧美成人一区二区三区| 免费在线亚洲| 国产在线拍偷自揄拍精品| 亚洲午夜久久久久久久久电影网| 日韩网站免费观看| 免费成人你懂的| 久久久五月天| 国产一区二区激情| 午夜欧美电影在线观看| 午夜精品久久久久久久久久久久久| 欧美精品综合| 亚洲精品久久久久久一区二区| 亚洲日本电影| 欧美激情精品久久久久久蜜臀| 欧美韩国一区| 亚洲欧洲一区二区在线观看| 免费精品99久久国产综合精品| 欧美成人小视频| 亚洲国产精品精华液网站| 可以免费看不卡的av网站| 欧美成年人网| 亚洲精品社区| 欧美日韩国产999| 亚洲三级影院| 中文久久精品| 国产精品久久久久毛片大屁完整版| 一本一本久久a久久精品综合妖精| 在线亚洲欧美视频| 国产精品第一区| 亚洲视频视频在线| 久久9热精品视频| 黄色亚洲在线| 免费成年人欧美视频| 亚洲人成网站777色婷婷| 日韩视频在线观看免费| 欧美日韩精品一区二区三区| 亚洲午夜精品久久| 久久午夜羞羞影院免费观看| 亚洲国产欧美一区| 欧美日韩视频一区二区| 亚洲欧美日韩精品久久亚洲区| 久久久免费精品| 亚洲精品国产日韩| 国产精品女主播一区二区三区| 欧美一级午夜免费电影| 欧美sm极限捆绑bd| 在线视频一区观看| 国产视频一区在线| 欧美大片在线观看一区二区| 一区二区三区精品视频在线观看| 久久九九全国免费精品观看| 亚洲毛片网站| 国产欧美日韩激情| 牛牛国产精品| 久久人体大胆视频| 欧美日韩精品不卡| 午夜综合激情| 欧美黄色一区| 午夜久久99| 亚洲欧洲视频| 国产农村妇女毛片精品久久麻豆 | 亚洲国产精品尤物yw在线观看| 欧美日韩成人综合天天影院| 香蕉亚洲视频| 亚洲精品黄色| 久久频这里精品99香蕉| 99视频精品免费观看| 国产亚洲欧美另类中文| 欧美国产日韩一二三区| 欧美一区二区国产| 99国产精品视频免费观看| 久久阴道视频| 亚洲欧美日韩在线高清直播| 亚洲国产精品久久久久婷婷老年 | 9i看片成人免费高清| 久久综合久久综合久久| 亚洲欧美自拍偷拍| 日韩视频免费观看高清完整版| 国产日韩欧美中文| 欧美性理论片在线观看片免费| 免费一级欧美片在线观看| 欧美一区二区三区视频| 一二三区精品福利视频| 亚洲国产欧美一区二区三区同亚洲 | 91久久精品www人人做人人爽| 久久成人18免费网站| 在线视频精品| 亚洲理伦电影| 亚洲国产经典视频| 黄色成人在线| 国产在线欧美日韩| 国产三级欧美三级日产三级99| 欧美日韩网址| 欧美日韩视频专区在线播放| 欧美国产欧美亚洲国产日韩mv天天看完整 | 国产精品视频最多的网站| 欧美精品亚洲精品| 美国十次了思思久久精品导航| 午夜在线成人av| 亚洲伊人网站| 亚洲午夜一级| 亚洲视频欧美在线| 宅男噜噜噜66一区二区| 一本久久青青| 99热在这里有精品免费| 亚洲麻豆一区| 99成人在线| 一区二区三区不卡视频在线观看 | 久久综合五月天婷婷伊人| 亚洲欧美在线x视频| 亚洲特色特黄| 亚洲综合日本| 亚洲欧美精品中文字幕在线| 亚洲在线一区二区| 亚洲欧美日韩国产一区二区| 亚洲一区二区欧美| 欧美一二三区在线观看| 欧美一区二区三区男人的天堂 | 欧美黄污视频| 欧美精品www| 欧美日韩一级视频| 国产精品麻豆va在线播放| 国产精品永久入口久久久| 国产亚洲一区二区三区| 亚洲成人在线视频网站| 亚洲经典视频在线观看| 亚洲毛片av| 亚洲免费视频网站| 久久精品日产第一区二区三区 | 狠久久av成人天堂| 亚洲国产日韩欧美在线99| 亚洲理伦电影| 午夜精品视频在线观看| 久久免费国产精品| 亚洲国产精品精华液2区45| 日韩视频在线观看免费| 亚洲免费视频成人| 久久综合伊人77777蜜臀| 欧美色欧美亚洲另类七区| 国产亚洲aⅴaaaaaa毛片| 亚洲国产精品成人va在线观看| 99精品热视频只有精品10| 午夜精品一区二区在线观看 | 国产日韩欧美麻豆| 最新高清无码专区| 午夜欧美不卡精品aaaaa| 美女性感视频久久久| 日韩视频精品| 久久精品卡一| 欧美三日本三级少妇三2023| 黑人一区二区三区四区五区| 亚洲蜜桃精久久久久久久| 久久精品国产久精国产爱| 亚洲国产精品女人久久久| 亚洲欧美日韩国产一区| 免费在线观看成人av| 国产美女一区二区| 99精品热视频| 蜜桃久久精品一区二区| 一区二区三区 在线观看视频| 久久久噜噜噜久久| 国产精品久久久久久久久久久久久| 亚洲电影在线播放| 欧美在线观看视频一区二区| 亚洲精品女人| 欧美中日韩免费视频| 国产精品草草| 日韩一级免费| 欧美a级大片| 午夜欧美大片免费观看| 国产精品超碰97尤物18|