随笔 - 87  文章 - 279  trackbacks - 0
<2007年11月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214292
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

对于扩展欧几里得主要部分说明:
1. d' = bx'+(a mod b)y', d' = gcd(b, a mod b);
    设 d = gcd(a, b), 因为 d = d', 所以
    d = d' = bx'+(a mod b)y' = bx' + (a-floor(a/b)*b)y' = ay'+b(x'-floor(a/b)y');
    故有迭代:
    x = y'; y = x'-floor(a/b)y';

对于解方程主要部分说明:
1.首先给出两个定理(证明请查看相关数论书):
   A. 方程 ax = b (mod n) 有解, 当且仅当 gcd(a, n) | b;
   B. 方程 ax = b (mod n) 有d个不同的解, 其中 d = gcd(a, n);
2.证明方程有一解是: x0 = x'(b/d) mod n;
   由 a*x0 = a*x'(b/d) (mod n)
         a*x0 = d (b/d) (mod n)   (由于 ax' = d (mod n))
                 = b (mod n)
   证明方程有d个解: xi = x0 + i*(n/d)  (mod n);
   由 a*xi (mod n) = a * (x0 + i*(n/d)) (mod n)
                             = (a*x0+a*i*(n/d)) (mod n)
                             = a * x0 (mod n)             (由于 d | a)
                             = b

代码如下:

#include <iostream>
#include 
<cmath>
using namespace std;

int egcd(int a, int b, int &x, int &y) {
    
if (b == 0) {
        x 
= 1; y = 0;
        return a;
    } 
else {
        
int tx, ty, d;
        d 
= egcd(b, a%b, tx, ty);
        x 
= ty; y = tx-a/b*ty;
        return d;
    }
}

void mels(
int a, int b, int n) {
    
int tx, ty, d, x0, i;
    d 
= egcd(a, n, tx, ty);
    
if (b%d==0) {
        x0 
= ((tx*b/d)%n+n)%n;
        
for (i=0; i<d; i++) {
            printf(
"%d ", (x0+i*n/d)%n);
        }
    } 
else {
        printf(
"No solutions!");
    }
    printf(
"\n");
}

int main() {
    mels(
1430100);
    return 
0;
}
posted on 2007-08-27 11:14 阅读(2169) 评论(2)  编辑 收藏 引用 所属分类: 算法&ACM

FeedBack:
# re: 解模线性方程小结 2007-09-18 10:17 drizzlecrj
这个模写的好,以前做那个青蛙跳,搞出了负数竟然能够ac~ 那题数据比较弱  回复  更多评论
  
# re: 解模线性方程小结 2008-09-10 12:05 mmlii
你好!谢谢你详细的解说,请问一下“(由于 ax' = d (mod n))
”是怎么来的?
在线等。。谢谢了  回复  更多评论
  

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