中国剩余定理及拓展

我好菜啊

中国剩余定理

我愿意称它为动动定理

有方程组：

[egin{cases}xequiv a_1 (mod p_1)\xequiv a_2 (mod p_2)\……\xequiv a_n (mod p_n)end{cases} ]

其中对于(iin[1,n],p_i)两两互质

求解：

定义(M=prodlimits_{i=1}^{n}p_i,M_i=frac{prodlimits_{j=1}^{n}p_j}{p_i})

则方程组的解为(sumlimits_{i=1}^{n}a_i*M_i*p_i^{-1})

证明：

观察(a_i*M_i*p_i^{-1})

对于(j e i)来说，由于(M_i)是(p_j)的倍数，所以(equiv 0(mod p_j))

对于(i)来说，由于(p_i)两两互质，所以(M_i)中不含(p_i)的倍数，且(a_i*M_i*p_i^{-1}equiv a_i(mod p_i))

code

给我也整一个

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
	inline int read()
	{
		int x=0;char ch,f=1;
		for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
		if(ch=='-') f=0,ch=getchar();
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
		return f?x:-x;
	}
	const int N=110;
	int n,m=1,x,y,ret;
	int a[N],p[N];
	inline void exgcd(int &x,int &y,int a,int b)
	{
		if(!b){x=1,y=0;return;}
		exgcd(y,x,b,a%b);
		y-=a/b*x;
	}
	inline void crt()
	{
		for(int i=1;i<=n;++i)
		{
			exgcd(x,y,m/p[i],p[i]);
			ret=(ret+m/p[i]*x%m*a[i]%m)%m;
		}
	}
	inline void main()
	{
		n=read();
		for(int i=1;i<=n;++i)
		{
			p[i]=read();
			a[i]=read()%p[i];
			m*=p[i];
		}
		crt();
		printf("%lld
",(ret%m+m)%m);
	}
}
signed main()
{
	red::main();
	return 0;
}

拓展中国剩余定理

有方程组：

[egin{cases}xequiv a_1 (mod p_1)\xequiv a_2 (mod p_2)\……\xequiv a_n (mod p_n)end{cases} ]

还是它！不过我们这次不保证(p_i)两两互质

我们选择关闭本题

求解：

其实我们可以数学归纳，假设我们已经求解出了前(k-1)个方程组的答案

重新定义(M=LCM_{i=1}^{k-1}p_i)，则前(k-1)个方程的解为(x+i*M(iin Z))

考虑与第(k)个方程合并，使得(x+t*Mequiv a_k(mod p_k))

去掉模数+移项得到(t*M+y*p_kequiv a_k-x)

我们用(exgcd)求出(t)，则前(k)个方程组的解为(x+t*M)

注意(exgcd)无解的情况

code

给我再整一个

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
	inline int read()
	{
		int x=0;char ch,f=1;
		for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
		if(ch=='-') f=0,ch=getchar();
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
		return f?x:-x;
	}
	const int N=1e5+10;
	int n,m,ret;
	int a[N],p[N];
	int x,y,g;
	inline void exgcd(int &x,int &y,int &g,int a,int b)
	{
		if(!b){x=1,y=0,g=a;return;}
		exgcd(y,x,g,b,a%b);
		y-=a/b*x;
	}
	inline int slow(int x,int k,int p)
	{
		int ret=0;
		while(k)
		{
			if(k&1) ret=(ret+x)%p;
			x=(x+x)%p;
			k>>=1;
		}
		return ret;
	}
	inline void excrt()
	{
		m=p[1],ret=a[1];
		for(int i=2;i<=n;++i)
		{
			int c=((a[i]-ret)%p[i]+p[i])%p[i];
			exgcd(x,y,g,m,p[i]);
			if(c%g);//无解
			x=slow(x,c/g,p[i]);
			ret+=x*m;
			m*=p[i]/g;
			ret=(ret+m)%m;
		}
	}
	inline void main()
	{
		n=read();
		for(int i=1;i<=n;++i) p[i]=read(),a[i]=read()%p[i];
		excrt();
		printf("%lld
",(ret%m+m)%m);
	}
}
signed main()
{
	red::main();
	return 0;
}