Peter_Matthew的博客

crt和excrt

2019-02-13

crt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1,y=0;return a;}
int t=exgcd(b,a%b,y,x);y-=a/b*x;return t;
}
int crt()
{
int ans=0,lcm=1,x,y;
for(int i=1;i<=k;i++)
lcm*=b[i];
for(int i=1;i<=k;i++)
{
int tp=lcm/b[i];
exgcd(tp,b[i],x,y);
x=(x%b[i]+b[i])%b[i];
ans=(ans+tp*x*a[i])%lcm;
}
return (ans+lcm)%lcm;
}

excrt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1,y=0;return a;}
int t=exgcd(b,a%b,y,x);y-=a/b*x;return t;
}
int excrt()
{
int x,y,k;
int M=b[1],ans=a[1];
for(int i=2;i<=n;i++)
{
int c=(a[i]-ans%b[i]+b[i])%b[i];
int gcd=exgcd(M,b[i],x,y),bg=b[i]/gcd;
if(c%gcd)return -1;
x=x*c/gcd%bg;
ans+=x*M;
M*=bg;
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}

知识共享许可协议

知识共享许可协议

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

标签: 述学
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章