The Fourth Dimension Space

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

浅究初等数论之中国剩余定理(Chinese Remainder Theorem)

 推论1:方程ax=b(mod n)对于未知量x有解,当且仅当gcd(a,n) | b。
 推论2:方程ax=b(mod n)或者对模n有d个不同的解,其中d=gcd(a,n),或者无解。
 定理1:设d=gcd(a,n),假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b,则方程ax=b(mod n)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n,方程ax=b(mod n)的最小整数解x1=e mod (n/d),最大整数解x2=x1+(d-1)*(n/d)。
 定理2:假设方程ax=b(mod n)有解,且x0是方程的任意一个解,则该方程对模n恰有d个不同的解(d=gcd(a,n)),分别为:xi=x0+i*(n/d) mod n 。


证明过程请详见 《算法导论》

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

int EXTENDED_EUCLID(int a,int b,int &x,int &y)//扩展欧几里德算法
{
    
if(b==0)
    
{
        x
=1;
        y
=0;
        
return a;
    }

    
int r=EXTENDED_EUCLID(b,a%b,x,y);
    
int temp=x;
    x
=y;
    y
=temp-a/b*y;
    
return r;
}


int  MODULAR_LINEAR(int a,int b,int n)//求解模线性方程
{
    
int d,x,y;
    
int x0;
    d
=EXTENDED_EUCLID(a,n,x,y);
    x0
=(x*(b/d)+n)%n;
    
return x0;
}

//当时鱼头让我们研究的时候,没有考虑得太仔细,上面的方程只能求出一个可行解
//而下面的函数能够求出最小的整数解,甚至在模n内任意的解
long long  MODULAR_LINEAR(long long a,long long b,long long n)//求解模线性方程
{
    
long long d,x,y;
    
long long x0;
    d
=EXTENDED_EUCLID(a,n,x,y);
    
if(b%d)
        
return -1;
    x0
=(x*(b/d))%n+n;//确保是正数
    x0%=(n/d);//x0是第一个大于0的整数解
    return x0;
}


int CHINESE_RESIDUE_THEOREM(int n[],int b[],int k)//求解模线性方程组,所有数据从1号下标开始存储
{

    
int result=0;
    
int i;
    
int N=1;
    
int *m=new int [k+1];
    
int *reversem=new int [k+1];
    
int sum=0;
    
for(i=1;i<=k;i++)
    
{
        N
*=n[i];
    }

    
for(i=1;i<=k;i++)
    
{

        m[i]
=N/n[i];
        reversem[i]
=MODULAR_LINEAR(m[i],1,n[i]);
        sum
+=m[i]*reversem[i]*b[i];
    }

    result
=sum%N;
    
return result;
}



int main ()
{

    
int num;
    
int i;
    printf(
"参考格式:X mod n[i] = b[i]\n");
    cout
<<"请输入方程的个数:";
    cin
>>num;
    
int *n=new int [num+1];
    
int *b=new int [num+1];
    
for(i=1;i<=num;i++)
    
{

        cout
<<"请输入第"<<i<<"个方程的n和b:";
        cin
>>n[i]>>b[i];
    }

    
int result=CHINESE_RESIDUE_THEOREM(n,b,num);
    cout
<<"解为:";
    cout
<<result<<endl;
    cout
<<"谢谢你的使用"<<endl;
    system(
"pause");
    
return 0;
}

posted on 2009-04-08 01:15 abilitytao 阅读(1589) 评论(0)  编辑 收藏 引用


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