JZTXT

同余

发布时间 2023-04-10 22:54:19作者: Liang2003

学习

中国剩余定理

\(ans=\sum_{i=1}^nM_i*r_i*t_i modM\)
其中\(M=\prod_1^nmod_i,M_i=\frac{M}{mod_i},t_i为M_i模M下的逆元\)

void solve() 
{
	cin>>n;
	int M=1;
	for(int i=1;i<=n;i++) cin>>mod[i]>>r[i],M=M*mod[i];
	int ans=0;
	int x,y;
	for(int i=1;i<=n;i++) 
	{
		int Mi=M/mod[i];
		ex_gcd(Mi,mod[i],x,y);
		ans=(ans+(Mi*x%M*r[i]%M)+M)%M;
	}
	cout<<ans%M<<endl;
}

扩展中国剩余定理

cin>>n;
	 for(int i=1;i<=n;i++) cin>>mod[i]>>r[i];
	 int x,y;
	 for(int i=1;i<n;i++) 
	 {
	 	int a=mod[i],b=mod[i+1],c=r[i+1]-r[i],g=gcd(a,b);
	 	if(c%g) {cout<<-1<<endl;return;}
	 	a/=g,b/=g,c/=g;
	 	ex_gcd(a,b,x,y);
	 	x=(x*c%b+b)%b;//非负最小整数解
	 	mod[i+1]=mod[i]/gcd(mod[i],mod[i+1])*mod[i+1];//mod[i+1]->lcm(mod[i],mod[i+1])
	 	r[i+1]=(mod[i]*x%mod[i+1]+r[i])%mod[i+1];//新的余数 r[i+1] = mod[i]*x+mod[i+1]*y 
	 }
	 //可能在某些题连longlong都会爆，这时候就要用龟速乘
	 cout<<r[n]<<endl;