中国剩余定理CRT

中国剩余定理是要求我们解决这样的一类问题：

\[\begin{cases}x\equiv a_1\pmod {b_1} \\x\equiv a_2 \pmod{b_2}\\...\\x\equiv a_n\pmod{b_n} \end{cases}
\]

其中\(b_1,b_2,...,b_n\)互质。

我们先令\(m=\prod_{i=1}^{n}b_i,w_i=m/b_i\)

那么有\(gcd(m,w_i)==1\)

我们对于\(w_ix'+my'= 1\)解出来\(x',y'\)后

\(w_ix'a_i\equiv a_i\pmod {b_i}\)

所以现在就相当于解\(n=\sum_{i=1}^n w_ix'a_i\pmod m\)

一道例题 TJOI2009猜数字

题目链接：戳我

CRT的模板

有两点需要注意——一个是输入的数可能会有负数，二是乘法的时候可能会乘爆，需要用快速乘qwq

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

#define MAXN 1010

using namespace std;

int n;

long long a[MAXN],b[MAXN];

inline ll fmul(ll x,ll y,ll mod)

{

	ll cur_ans=0;

	while(y>0)

	{

		if(y&1)cur_ans=(cur_ans+x)%mod;

		x=(x+x)%mod;

		y>>=1;

	}

	return cur_ans;

}

inline void exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b==0){y=0,x=1;return;}

	exgcd(b,a%b,x,y);

	int cur=x;

	x=y;

	y=cur-a/b*y;

}

inline ll china()

{

	long long M=1,cur_ans=0,x,y;

	for(int i=1;i<=n;i++) M*=b[i];

	for(int i=1;i<=n;i++)

	{

		long long w=M/b[i];

		exgcd(w,b[i],x,y);

		x=(x%b[i]+b[i])%b[i];

		cur_ans=(cur_ans+fmul(fmul(w,x,M),a[i],M))%M;

	}

	return (cur_ans+M)%M;

}

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("ce.in","r",stdin);

	#endif

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);

	for(int i=1;i<=n;i++) a[i]=(a[i]%b[i]+b[i])%b[i];

	printf("%lld\n",china());

	return 0;

}

拓展中国剩余定理EXCRT

就是\(b_i\)不互质版本的......但是和中国剩余定理好像没有太大的关系qwq

我们假设已经解决了前k-1个方程，他们的解为ans，设\(m=\prod_{i=1}^{k-1}b_i\)。那么我们可以确定前k-1个方程的通解是\(ans+t*m\)。

现在的任务就是寻找一个t，使得\(ans+t*m\equiv a_i\pmod{b_i}\)

也就是\(t*m\equiv a_i-ans\pmod{b_i}\)

其实就是解\(a\equiv b\pmod {p}\)即\(ax+py=b\)的\(x',y'\)的解。

\(t=x'/gcd(m,b_i)*(a_i-ans)\)

\(ans=(ans+tm)\mod (\prod_{i=1}^{k-1}b_i)\)

一道模板

题目链接：戳我

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100010

#define ll long long

using namespace std;

int n;

long long a[MAXN],b[MAXN];

inline ll fmul(ll x,ll y,ll mod)

{

	ll cur_ans=0;

	while(y)

	{

		if(y&1) cur_ans=(cur_ans+x)%mod;

		x=(x+x)%mod;

		y>>=1;

	}

	return cur_ans;

}

inline ll exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b==0)

	{

		y=0,x=1;

		return a;

	}

	ll ans=exgcd(b,a%b,x,y);

	ll cur=x;

	x=y;

	y=cur-(a/b)*y;

	return ans;

}

inline void solve()

{

	ll ans=a[1],m=b[1],x,y;

	for(int i=2;i<=n;i++)

	{

		ll B=((a[i]-ans)%b[i]+b[i])%b[i];

		ll gcd=exgcd(m,b[i],x,y);

		x=fmul(x,B/gcd,b[i]);

		ans+=x*m;

		m*=b[i]/gcd;

		ans=(ans+m)%m;

	}

	printf("%lld\n",ans);

}

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("ce.in","r",stdin);

	#endif

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%lld%lld",&b[i],&a[i]);

//	for(int i=1;i<=n;i++) printf("%lld %lld\n",a[i],b[i]);

	solve();

	return 0;

}

巴特西

CRT和EXCRT简单学习笔记

中国剩余定理CRT

一道例题 TJOI2009猜数字

题目链接：戳我

拓展中国剩余定理EXCRT

一道模板

题目链接：戳我

最新文章

热门文章