同余方程

问题描述

方程组：
(x equiv a_1 ( mod:m_1))
(x equiv a_2(mod:m_2))
····
(x equiv a_k(mod: m_k))
求解x

求解

首先考虑前两个式子
(x=m_1cdot y_1+a_1=m_2cdot y_2+a_2)
则(m_1y_1-m_2y_2=a_2-a_1)（有解当且仅当((m_1,m_2)|a_2-a_1))
(y_1=y_0+frac{km_2}{(m_1,m_2)}(kin Z))
则(x=m_1y_0+frac{km_1m_2}{(m_1,m_2)}+a_1),设(x'=m_1y_0+a_1)
则(x=x'+k[m_1,m_2] ([m_1,m_2]为最小公倍数))
所以得到新的式子(xequiv x'(mod :[m_1m_2]))
则原来方程组方程数目减一
以此类推，得到(xequiv x'' (mod :[m_1m_2m_3]))
继续下去便得到x的解

poj2891
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
const int maxn=10000000+101;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	return x*f;
}
int k;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
	if(!b){d=a;x=1;y=0;return ;}
	exgcd(b,a%b,d,x,y);
	ll t=x;x=y;y=t-(a/b)*y;
	return ;
}
int main(){
	while(scanf("%d",&k)!=EOF){
		ll a1=read(),r1=read(),a2,r2;
		bool fa=false;
		for(int i=2;i<=k;i++){
			a2=read();r2=read();
			if(fa)continue;
			ll d,x,y,c=r1-r2;
			exgcd(a2,a1,d,x,y);
			if(c%d){fa=true;continue;}
			x=x*(c/d);
			a1/=d;
			x=(x%a1+a1)%a1;//求最小整数解
			x=(x*a2+r2); 
			a1=a1*a2;
			r1=((x%a1)+a1)%a1;
		}
		if(fa)printf("-1
");
		else printf("%lld
",r1);
	}
	return 0;
}

孙子定理

问题描述：

设(m_1,m_2,···,m_k)是两两互质的k个正整数
方程组：
(xequiv a_1(mod : m_1))
(xequiv a_2(mod :m_2))
····
(xequiv a_k(mod :m_k))
设(M=m_1m_2···m_k,M_i=frac{M}{m_i},M_i^{'}M_iequiv 1(mod : m_i))
则解(xequiv sum_{i=1}^{k}M_i^{'}M_ia_i(mod : M))

证明

设(x=u_1a_1+u_2a_2+···+u_ka_k)
显然要满足方程组，则等价于(x=M_1v_1a_1+M_2v_2a_2+····+M_kv_ka_k)
当(v_i=M_i'时，x满足方程组，所以求得解x)