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

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 閱讀(798) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithmMathematics課內(nèi)作業(yè)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品一级久久久| 亚洲国产成人久久| 在线播放视频一区| 伊人成年综合电影网| 一区二区亚洲精品| 91久久精品国产91久久性色tv | 久久久久国产一区二区| 性8sex亚洲区入口| 久久综合导航| 亚洲人成在线播放网站岛国| 亚洲深夜福利视频| 久久久精彩视频| 欧美黄色网络| 国产日韩一区二区三区| 黄色国产精品| 亚洲精品久久久久| 亚洲你懂的在线视频| 久久天堂av综合合色| 亚洲精品视频在线播放| 亚洲欧美久久久久一区二区三区| 久久精品二区三区| 欧美韩日一区| 国产综合色一区二区三区| 亚洲欧洲中文日韩久久av乱码| 中文欧美字幕免费| 久久琪琪电影院| 亚洲毛片在线| 久久夜色精品亚洲噜噜国产mv | 国产揄拍国内精品对白| 亚洲开发第一视频在线播放| 欧美在线免费观看| 亚洲精品国产精品久久清纯直播 | 亚洲日本电影在线| 欧美在线视频在线播放完整版免费观看 | 亚洲高清网站| 午夜精品婷婷| 欧美激情精品久久久久| 亚洲少妇自拍| 欧美激情 亚洲a∨综合| 黄色亚洲网站| 久久精品综合| 午夜精品一区二区三区在线| 欧美视频精品在线| 日韩一级大片| 欧美第一黄网免费网站| 欧美综合二区| 国产一区91精品张津瑜| 亚洲女人天堂成人av在线| 亚洲国产裸拍裸体视频在线观看乱了 | 久久av一区二区| 一区二区三区久久网| 欧美成人有码| 亚洲高清在线观看一区| 久久青草欧美一区二区三区| 亚洲免费小视频| 国产精品日本欧美一区二区三区| 一区二区三欧美| 亚洲精品乱码久久久久久| 欧美成年人视频网站| 最新日韩欧美| 亚洲人成人一区二区在线观看| 久久视频精品在线| 亚洲国产美女久久久久| 另类av一区二区| 久久久久久欧美| 亚洲国产成人av在线| 欧美99久久| 欧美激情精品久久久久久变态| 亚洲欧洲视频| 99国内精品| 国产精品一区二区在线观看不卡| 亚洲裸体视频| 亚洲精品乱码久久久久久久久| 欧美精品三级| 亚洲欧美另类久久久精品2019| 亚洲午夜三级在线| 国产亚洲精品久| 免费亚洲电影在线| 欧美精选在线| 欧美在线视频在线播放完整版免费观看 | 亚洲一级免费视频| 国产精品99久久99久久久二8 | 91久久精品国产91性色| 国产综合精品一区| 久久精品国产99国产精品澳门 | 亚洲国产欧美一区| 亚洲欧洲日产国产综合网| 欧美18av| 午夜视频在线观看一区二区| 欧美一区二区三区电影在线观看| 在线观看亚洲视频啊啊啊啊| 欧美成人有码| 国产精品国产a级| 久久另类ts人妖一区二区| 久久伊伊香蕉| 亚洲综合第一| 久久乐国产精品| 亚洲欧美日韩国产中文 | 亚洲欧美一级二级三级| 影音先锋亚洲视频| 在线亚洲精品福利网址导航| 韩国三级在线一区| 亚洲精品视频在线观看免费| 国产亚洲综合在线| 夜夜嗨av一区二区三区网站四季av| 国产欧美日韩一区二区三区在线观看| 欧美成人一区二区| 国产精品制服诱惑| 欧美福利视频一区| 国产伦精品一区二区三区在线观看 | 亚洲在线一区二区三区| 亚洲精品久久久久久久久久久久久| aa亚洲婷婷| 伊人久久久大香线蕉综合直播| 亚洲裸体在线观看| 亚洲国产日韩欧美在线99| 亚洲综合电影| 日韩亚洲欧美在线观看| 久久免费国产精品| 久久亚洲精品网站| 国产三级精品在线不卡| 在线综合亚洲欧美在线视频| 亚洲日本无吗高清不卡| 久久国产精品99国产| 亚洲淫片在线视频| 欧美国产日本| 亚洲国产精品va在线看黑人动漫 | 亚洲精品视频免费| 久久最新视频| 久久嫩草精品久久久精品| 国产精品老牛| 欧美成人在线免费观看| 亚洲久久一区二区| 久久激情综合网| 久久免费高清视频| 国产精品系列在线| 亚洲网在线观看| 亚洲综合社区| 国产精品美女久久久久久免费| 日韩视频不卡中文| 亚洲一级片在线看| 国产精品igao视频网网址不卡日韩| 亚洲国产美女久久久久| 亚洲激情视频网| 欧美粗暴jizz性欧美20| 亚洲黄色av| 亚洲宅男天堂在线观看无病毒| 欧美日韩一区二区三| 亚洲最黄网站| 欧美一区二区三区免费看| 国产一区二区三区无遮挡| 久久国产欧美| 免费亚洲网站| 亚洲小说春色综合另类电影| 欧美视频在线免费| 欧美一级久久| 欧美高清视频一二三区| 一本色道精品久久一区二区三区| 欧美日韩综合另类| 亚洲专区一二三| 玖玖在线精品| 99精品免费视频| 国产日韩精品电影| 免费欧美电影| 在线综合亚洲| 欧美大片免费看| 亚洲欧美国产制服动漫| 在线观看国产成人av片| 欧美三级日本三级少妇99| 欧美一区二区三区另类| 亚洲国产精品久久人人爱蜜臀| 亚洲欧美久久久久一区二区三区| 一区二区视频在线观看| 欧美日韩成人在线播放| 欧美一级黄色网| 一本色道久久加勒比88综合| 久久久久久综合| 亚洲视频在线看| 亚洲国产精品久久久久| 国产欧美一区二区精品婷婷| 欧美激情一区二区三区高清视频| 亚洲欧美成人网| 亚洲人成网站在线播| 久久这里只有精品视频首页| 亚洲午夜羞羞片| 亚洲精品国精品久久99热一| 国产一区观看| 国产精品婷婷午夜在线观看| 欧美黑人国产人伦爽爽爽| 欧美一区二区高清| 一区二区三区波多野结衣在线观看| 欧美a一区二区| 久久天天躁狠狠躁夜夜av| 欧美亚洲视频| 亚洲视频1区2区| 日韩视频免费在线观看| 亚洲国产一区二区三区高清| 国产亚洲制服色| 国产一区二区| 国产一区二区三区日韩|