● 中国剩余定理解模线性方程组 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: ACMICPC
标  题: 中国剩余定理解模线性方程组
发信站: 荔园晨风BBS站 (Sun Jul 25 15:01:10 2004), 站内信件

自行看数论的知识，看完后，可以尝试做做zoj上面的1005

希望能看到各位不断accept的好消息

//解模线性方程组  中国剩余定理
//by jhun
//May 4th 2003
#include <stdio.h>

//计算和返回d=gcd(a,b)和满足ax+by=d的值x和y,其中y为b在模a下的乘法逆元
int Extender_Enclid(int a, int b, int &x, int &y)
{
        int t,t1;
        if (b==0)
        {
                x=1, y=0;
                return a;
        }
        else
        {
                t1 = Extender_Enclid(b, a%b, x, y);
                t=x; x=y; y=t-(a/b)*y;
                return t1;
        }
}

/*
* r is the number of elements in arrays m and u
* m is the array of (pairwise relatively prime) moduli
* u is the array of coefficients
* return value is n such that
* n == u[k] % m[k] (k=0..r-1) and n < m[0]*m[1]*...*m[r-1]
*/
int China(int r,int *m,int *u)
{
        int d,x,y,n,m_i,i,a;

        for(n=1,i=0;i<r;i++)    n *= m[i];
        a=0;
        for(i=0;i<r;i++)
        {
                m_i = n / m[i];
                d = Extender_Enclid( m[i], m_i, x, y );
                     //通过扩展的欧几里得算法求m_i的逆元y
                a = ( a + y * m_i * u[i] ) % n;
        }
        if(     a>0 )   return a;
        else            return a+n;
}

int main()
{
        const int r=3;
        int m_i[r]={3,5,7},u_i[r]={2,3,2},n;
        //n==u[i]%m[i] i=0...r-1

        n = China(r,m_i,u_i);
        printf("%d\n",n);
        return 0;
}
--

菩提本无树，明镜亦非台

本来无一物，何处惹尘埃

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.21.224.234]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店