The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

使用中国剩余定理中处理某些方程模数不互质的方法

##Update 2010-4-16
这里稍微证明一下:
给定方程
x = c1 (mod b1) ……………………(1)
x = c2(mod b2) ………………………(2)
(b1,b2)可以不为1
于是通过取mod 定义,我们得到

x = k1 * b1 + c1………………(3)
(3) 带入(2)
k1 * b1 + c1 = c2 (mod b2)…………(4)
化简
k1 * b1 = c2 - c1 (mod b2)…………(5)
于是可以解得到
令G = gcd(b1,b2),C = c2 - c1 (mod b2)
那么由(5)得到
k1 * b1 = W * b2 + C
---->>>>>
k1 * b1 / G = W * b2 / G + C / G
令C'  = C/G
k1 * b1 / G = W * b2 / G + C '
k1 * b1 / G = C' (mod b2 / G)
--->
k1 = K (mod b2/G)………………(6)

那么有
k1 = k' * b2/G + K………………(7)
(7)带入(3)
x = k' * b2 * b1/G + K * b1 + c1………………(8)

x = K*b1 + c1 (mod b1 * b2/G)

通过合并方程的方法成功AC下面此题

题目地址
#include<iostream>
#include
<cmath>
using namespace std;
//x = c1 ( mod b1)
//x = c2 ( mod b2)
//若可以可并,则返回合并结果,否则返回-1可以处理gcd(b1,b2)!=1的情况
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ext_gcd(int a,int b,int& x,int& y){
    
int t,ret;
    
if (!b){
        x
=1,y=0;
        
return a;
    }

    ret
=ext_gcd(b,a%b,x,y);
    t
=x,x=y,y=t-a/b*y;
    
return ret;
}

//求a对n的乘法逆元,若不存在返回-1
int Invmod(int a,int n){
    
int x,y;
    
if (ext_gcd(a,n,x,y)!=1)return -1;
    
return (x%n+n)%n;
}

int mergef(int b1,int c1,int b2,int c2,int &b,int &c)
{
    
int tb1=b1,tb2=b2;
    c
=((c2-c1)%b2+b2)%b2;
    
int G=gcd(b1,b2);
    
if(c%G)return 0;
    c
/=G;
    b1
/=G;
    b2
/=G;
    c
*=Invmod(b1,b2);
    c
%=b2;
    c
*=tb1;
    c
+=c1;
    b
=tb1*tb2/G;
    c
%=b;
    
return 1;
}

int main()
{
    
int b1,b2,c1,c2,b,c;
    
while(cin>>b1>>c1>>b2>>c2)
    
{
        
if(mergef(b1,c1,b2,c2,b,c))
            cout
<<"X = "<<c<<' '<<"(mod "<<b<<')'<<endl;
    }

    
return 0;
}

扩充了算法导论中中国剩余定理部分的内容,使得它可以处理更一般的情况了,这个模板具有通用性。
转自:http://hi.baidu.com/aekdycoin/blog/item/71d7a842b93f611b73f05da4.html
顺便提一下,除了整理模板之外,要开始网络流部分的强化训练了,强化构图能力。

posted on 2010-08-26 23:32 abilitytao 阅读(710) 评论(0)  编辑 收藏 引用


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