荔园在线
荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: huhaiming (一生只爱她), 信区: Program
标 题: 中国剩余定理解模线性方程组
发信站: 荔园晨风BBS站 (Sun Jul 25 15:01:55 2004), 转信
【 以下文字转载自 ACMICPC 讨论区 】
【 原文由 huhaiming 所发表 】
自行看数论的知识,看完后,可以尝试做做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站 bbs.szu.edu.cn·[FROM: 210.21.224.234]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店