早就見識過這類的題目了，但是一直不會，看不太懂
昨天仔細研究了一下
結合前邊學的擴展歐幾里德一下就會了
模板寫的還不錯
在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ǎ崽 閱讀(718)
評論(0) 編輯 收藏 引用