coreBugZJ

此 blog 已弃。

EOJ 1056 线性同余方程

  1/*
  2EOJ 1056 线性同余方程
  3
  4
  5----问题描述:
  6
  7形如ax≡b(mod m) 的方程,称为线性同余方程。编写程序求解线性同余方程(基于欧几里德算法)。
  8
  9
 10----输入:
 11
 12测试包含多组测试数据.
 13每组测试数据只含一行,每行有三个整数a,b,m(0<a,b,m<1000000)
 14
 15
 16----输出:
 17
 18每组测试数据只输出一行.如果有解,则按解的大小,从小到大输出,两两之间用空格分开.如果没有解,则输出"No Answer."(不含引号).
 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扩展欧几里得算法:
 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当且仅当 b % gcd(a, m) == 0 时有解
 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 阅读(750) 评论(0)  编辑 收藏 引用 所属分类: ACMAlgorithmMathematics课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理