[note]CRT&exCRT

中国剩余定理

别人的blog
假设现在有关于x的同余方程组(p1,p2均为质数)
(x=a_1pmod {p_1})
(x=a_2pmod {p_2})
可以转化成如下形式
(x=a_1+k_1p_1)
(x=a_2+k_2p_2)
联立就有(a_1+k_1p_1=a_2+k_2p_2)
显然可以扩欧求一组特解,设为(k_1',k_2')
那么全部的解可以表示成
(k_1=k_1'+p_2t)
(k_2=k_2'+p_1t)
其中t为整数
回带就有(x=a_1+(k_1'+p_2t)p_1=a_1+p_1k_1'+p_1p_2t)
设(x_0=a_1+p_1k_1')就有(x=x_0pmod{p_1p_2})
那么如果有多组方程,我们就可以按照上面的方法合并方程,最后只剩一个
即(x=x_0pmod{p_1p_2...p_n})
例题1[TJOI2009]猜数字
例题2曹冲养猪

#define ll long long
#include<bits/stdc++.h>
using namespace std;
int n;
ll a[20],b[20];
void exgcd(ll a,ll b,ll&x,ll&y){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b,x,y);
    ll t=x;x=y;y=t-a/b*y;
}
ll crt(){
    ll A=a[1],B=b[1],x,y;
    for(int i=2;i<=n;i++){
        exgcd(A,a[i],x,y);
        x*=((b[i]-B)%a[i]+a[i])%a[i];//不定方程ax+by=c两边同时加上b的倍数,x的结果不改变
        B+=A*x;A*=a[i];B=(B%A+A)%A;//注意到x有可能为负,所以每次把B模一下A把负的转成正的
    }
    return B;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    cout<<crt()<<endl;
    return 0;
}

---

扩展CRT

用于解决模数不互质的情况(这么多ex都是模数不互质...),
还是先考虑两个方程
(x_1=a_1pmod {m_1})
(x_2=a_2pmod {m_2})
联立得(a_1+k_1m_1=a_2+k_2m_2)
当(gcd(m_1,m_2))不整除((a_1-a_2))时是无解的
如果有解,那么可以改成(frac{a_1-a_2}{gcd(m_1,m_2)}=k_2frac{m_2}{gcd(m_1,m_2)}-k_1frac{m_1}{gcd(m_1,m_2)})
继续exgcd求解,按照CRT的推法,最终能得到(x=x_0pmod{lcm(m_1,m_2,...,m_n)})
[模板]扩展中国剩余定理

#define ll long long
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
ll re(){
	ll x=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*w;
}
int n;
ll a[N],m[N];
ll exgcd(ll a,ll b,ll&x,ll&y){
	if(!b){x=1,y=0;return a;}
	ll g=exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-a/b*y;
	return g;
}
ll ksc(ll x,ll y,ll p){
	ll s=0;
	while(y){
		if(y&1)s=(s+x)%p;
		x=(x+x)%p;
		y>>=1;
	}
	return s;
}
ll excrt(){
	ll M=m[1],A=a[1],d,a1,b1,g,x,y;
	for(int i=2;i<=n;i++){
		a1=M,b1=m[i],d=((a[i]-A)%b1+b1)%b1;
		g=exgcd(a1,b1,x,y);
		x=ksc(x,d/g,b1);A+=x*M;M=M*(b1/g);
		A=(A%M+M)%M;
	}
	return (A%M+M)%M;
}
int main(){
	n=re();
	for(int i=1;i<=n;i++)
		m[i]=re(),a[i]=re();
	printf("%lld
",excrt());
	return 0;
}