The Fourth Dimension Space

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

中国剩余定理

#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;
}

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-07-14 16:27 abilitytao 阅读(180) 评论(0)  编辑 收藏 引用


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