早就见识过这类的题目了，但是一直不会，看不太懂
昨天仔细研究了一下
结合前边学的扩展欧几里德一下就会了
模板写的还不错
在OJ上做了两道题目
http://acm.hdu.edu.cn/showproblem.php?pid=1930http://acm.hdu.edu.cn/showproblem.php?pid=1370模板如下
void Extended_gcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x = 1;
y = 0;
return ;
}
Extended_gcd(b,a%b,x,y);
int t = x;
x = y;
y = t - a/b*x;
}
int china_mod(int mod[],int a[])
{
int lcm,i,ans,Mi,x,y;
lcm = 1;
for(i=0;i<n;i++)
lcm *= mod[i];
ans = 0;
for(i=0;i<n;i++)
{
Mi = lcm/mod[i];
Extended_gcd(Mi,mod[i],x,y);
ans += Mi*x*a[i];
}
ans %= lcm;
while(ans<0)
ans += lcm;
return ans;
}
posted on 2009-03-11 11:24
shǎ崽 阅读(701)
评论(0) 编辑 收藏 引用