[转]标程: 线性同余方程的求解

喜欢ヅ旅行 2022-08-04 13:53 166阅读 0赞

因为ACM/ICPC中有些题目是关于数论的，特别是解线性同余方程，所以有必要准备下这方面的知识。关于这部分知识，我先后翻看过很多资料，包括陈景润的《初等数论》、程序设计竞赛例题解、“黑书”和很多网上资料，个人认为讲的最好最透彻的是《算法导论》中的有关章节，看了之后恍然大悟。经过几天的自学，自己觉得基本掌握了其中的“奥妙”。拿出来写成文章。

那么什么是线性同余方程？对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值。

解题例程：[pku1061 青蛙的约会 解题报告][pku1061 _]

符号说明：

mod表示：取模运算

ax≡b(mod m)表示：(ax - b) mod m = 0，即同余

gcd(a,b)表示：a和b的最大公约数

求解ax≡b(mod n)的原理：

对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法，见下面的MLES算法。

第一个问题：求解gcd(a,b)

定理一：gcd(a,b) = gcd(b,a mod b)

实现：古老的欧几里德算法

int Euclid(int a,int b)  
\{  
if(b == 0)  
return a;  
else  
return Euclid(b,mod(a,b));  
\}

附：取模运算

int mod(int a,int b)  
\{  
if(a >= 0)  
return a % b;  
else  
return a % b + b;  
\}

第二个问题：求解ax + by = gcd(a,b)

定理二：gcd(b,a mod b) = b \* x' + (a mod b) \* y'

= b \* x' + (a - a / b \* b) \* y'

= a \* y' + b \* (x' - a / b \* y')

= a \* x + b \* y

则：x = y'

y = x' - a / b \* y'

实现：

triple Extended\_Euclid(int a,int b)  
\{  
triple result;  
if(b == 0)  
\{  
result.d = a;  
result.x = 1;  
result.y = 0;  
\}  
else  
\{  
triple ee = Extended\_Euclid(b,mod(a,b));  
result.d = ee.d;  
result.x = ee.y;  
result.y = ee.x - (a/b)\*ee.y;  
\}  
return result;  
\}

附：三元组triple的定义

struct triple  
\{  
int d,x,y;  
\};

第三个问题：求解ax≡b(mod n)

实现：由x，y堆砌方程的解

int MLES(int a,int b,int n)  
\{  
triple ee = Extended\_Euclid(a,n);  
if(mod(b,ee.d) == 0)  
return mod((ee.x \* (b / ee.d)),n / ee.d);  
else  
return -1;  
\}//返回-1为无解，否则返回的是方程的最小解

说明：ax≡b(mod n)解的个数：

如果ee.d 整除 b 则有ee.d个解；

如果ee.d 不能整除 b 则无解。

附:

![1.jpg][]

[pku1061 _]: http://hi.baidu.com/redcastle/blog/item/e6dc30d3a5574d023af3cfe0.html
[1.jpg]: /images/20220731/52f40ba6254b417d873bdace17725b18.png