• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

扩展中国剩余定理(EXCRT)学习笔记

开发技术 开发技术 2周前 (04-07) 12次浏览

扩展中国剩余定理(EXCRT)学习笔记

用途

求解同余方程组

(begin{cases}xequiv c_{1}left( mod m_{1}right) \ xequiv c_{2}left( mod m_{2}right) \ ldots \ xequiv c_rleft( mod m_rright) end{cases})

其中 (m_1,m_2,m_3…m_k) 为不一定两两互质的整数, 求 (x) 的最小非负整数解。

求法

考虑两两合并同余方程,使得新得到的同余方程满足之前两个同余方程的限制条件。

这样合并到最后只剩下一个同余方程直接输出答案即可。

对于两个同余方程 (x%a_1=b_1,x%a_2=b_2)

(x=k_1a_1+b_1,x=k_2a_2+b_2)

那么有 (k_1a_1+b_1=k_2a_2+b_2)

(k_1a_1-k_2a_2=b_2-b_1)

(d=gcd(a_1,a_2)),如果 ((b_2-b_1)%d ne 0),那么无解。

否则对于方程两边同时除以 (d)

(k_1frac{a_1}{d}-k_2frac{a_2}{d}=frac{b_2-b_1}{d}),

(k_1frac{a_1}{d}=frac{b_2-b_1}{d}+k_2frac{a_2}{d})

可以看作 (k_1frac{a_1}{d}%frac{a_2}{d}=frac{b_2-b_1}{d})

(inv=frac{a_1}{d} % frac{a_2}{d}) 意义下的逆元,

对于方程两边同时乘 (inv)

(k_1%frac{a_2}{d}=frac{inv(b_2-b_1)}{d})

展开后有 (k_1=frac{inv(b_2-b_1)}{d}+k_2frac{a_2}{d})

代入开始的 (x=a_1k_1+b_1)

(x=frac{a_1inv(b_2-b_1)}{d}+k_2frac{a_1a_2}{d}+b_1)

(frac{a_1a_2}{d}) 看成新的 (a),把 (frac{a_1inv(b_2-b_1)}{d}+b_1) 看成新的 (b) 即可。

代码

【模板】扩展中国剩余定理(EXCRT)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define rg register
template<typename T>void read(rg T& x){
	x=0;rg int fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=fh;
}
const int maxn=1e5+5;
int n;
long long a[maxn],b[maxn];
long long gcd(rg long long aa,rg long long bb){
	return bb==0?aa:gcd(bb,aa%bb);
}
long long lcm(rg long long aa,rg long long bb){
	return aa/gcd(aa,bb)*bb;
}
long long exgcd(rg long long aa,rg long long bb,rg long long&xx,rg long long&yy){
	if(bb==0){
		xx=1,yy=0;
		return aa;
	}
	rg long long nans=exgcd(bb,aa%bb,xx,yy);
	rg long long t=xx;
	xx=yy;
	yy=t-aa/bb*yy;
	return nans;
}
long long getinv(rg long long val,rg long long mod){
	rg long long xx,yy;
	exgcd(val,mod,xx,yy);
	return (xx%mod+mod)%mod;
}
long long gsc(rg long long ds,rg long long zs,rg long long mod){
    return ((unsigned long long)(ds*zs)-(unsigned long long)((long double)ds/mod*zs)*mod+mod)%mod;
}
int main(){
	read(n);
	for(rg int i=1;i<=n;i++) read(a[i]),read(b[i]);
	rg long long newa,newb,tmp;
	for(rg int i=2;i<=n;i++){
		newa=lcm(a[i],a[i-1]),tmp=gcd(a[i],a[i-1]);
		newb=gsc((b[i]-b[i-1])/tmp,getinv(a[i-1]/tmp,a[i]/tmp),newa);
		newb=gsc(newb,a[i-1],newa)+b[i-1];
		newb=(newb%newa+newa)%newa;
		a[i]=newa,b[i]=newb;
	}
	printf("%lldn",b[n]);
	return 0;
}

程序员灯塔
转载请注明原文链接:扩展中国剩余定理(EXCRT)学习笔记
喜欢 (0)