学习笔记：中国剩余定理（CRT）

引入

常想起在空间里见过的一些智力题，这个题你见过吗：

一堆苹果，\(3\)个\(3\)个地取剩\(1\)个，\(5\)个\(5\)个地取剩\(1\)个，\(7\)个\(7\)个地取剩\(2\)个，苹果最少有几个？

够焦头烂额的（雾

大力算可知至少有16个。

我们把它抽象成数学问题：

求满足

\[\begin{cases}x\equiv1\pmod{3}\\x\equiv1\pmod{5}\\x\equiv2\pmod{7}\end{cases}
\]

的最小正整数\(x\)。

感性地猜到有一个长为\(3×5×7=105\)的循环节，至于为啥，一会就知道了。

求解

(下面是老祖宗神奇的思维，别问我为什么)

构造方程组：

\[\begin{cases}x\equiv0\pmod{3}\\x\equiv0\pmod{5}\\x\equiv1\pmod{7}\end{cases}
\]

显然这里\(x\)可表示为\(15y(y\in Z)\)，即：

\[15y\equiv1\pmod{7}
\]

可得（不就是乘法逆元吗？）：

\[15y\equiv1\pmod{7} \xrightarrow{}y\equiv1\pmod{7}\xrightarrow{}y_{min}=1\xrightarrow{}x_{min}=15
\]

同理构造三个方程，解(\(x\))分别为：\(15,70,21\)。

再乘上余数即可（记得取模）：

\[ans=15×2+70×1+21×1=121\equiv16\pmod{3×5×7=105}
\]

最后的答案即为同余号右边的数。

这样可以用代码实现：

题目链接：P1495 【模板】中国剩余定理(CRT)/曹冲养猪

\(Code\):

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

int n;

ll a[15],b[15];

ll sum=1,now=1,ans=0,rt=1;

ll x,y;

inline void exgcd(ll a,ll b)

{

	if(b==0)

	{

		x=1,y=0;

		return;

	}

	exgcd(b,a%b);

	ll t=x;

	x=y;

	y=t-a/b*y;

}

int main()

{

	scanf("%d",&n);

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

	for(int i=1;i<=n;i++) rt=rt*a[i];

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

	{

		sum=now=1;

		for(int j=1;j<=n;j++) if(i!=j) now=now*a[j],sum=sum*a[j]%a[i];

		exgcd(sum,a[i]);

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

		ans=(ans+b[i]*x*now)%rt;

	}

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

	return 0;

}

复杂度是\(O(n^2+nlogn)\)，对于此题\(n=10\)的数据，足以。

优化

有什么更好的方法？

用\(n-1\)次中国剩余定理！

其实就是。

看样例：

我们先求解：

\[\begin{cases}x\equiv1\pmod{3}\\x\equiv1\pmod{5}\end{cases}
\]

我们知道，最后的得数还是同余方程，比如上边样例得出的：

\[x\equiv16\pmod{105}
\]

这类似一个合并过程，我们把两个方程合并成一个即可，如：

\[\begin{cases}x\equiv1\pmod{3}\\x\equiv1\pmod{5}\end{cases}
\]

可合并为：

\[x\equiv8\pmod{15}
\]

再与下一个方程合并即可，这样的合并仅是\(O(2logn)\)的，不过似乎正解是\(O(logn)\)，差不多了......

\(Code\):

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

int n;

struct node

{

	ll a,b;

}e[15];

ll sum=1,now=1,ans=0,rt=1;

ll x,y;

inline void exgcd(ll a,ll b)

{

	if(b==0)

	{

		x=1,y=0;

		return;

	}

	exgcd(b,a%b);

	ll t=x;

	x=y;

	y=t-a/b*y;

}

node merge(node m,node n)

{

	node ans;

	ans.a=m.a*n.a;

	exgcd(n.a%m.a,m.a);

	ll l=(x%m.a+m.a)%m.a;

	l=l*m.b%ans.a*n.a%ans.a;

	exgcd(m.a%n.a,n.a);

	ll r=(x%n.a+n.a)%n.a;

	r=r*n.b%ans.a*m.a%ans.a;

	ans.b=(l+r)%ans.a;

	return ans;

}

int main()

{

	scanf("%lld",&n);

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

	node o=e[1];

	for(int i=2;i<=n;i++) o=merge(o,e[i]);

	printf("%lld\n",o.b);

	return 0;

}

不过码量大一些，我想这么小的数据就不必了吧。

（这一部分在题解区没有，不想放上）

\(upd:2020.2.29(\text{真是特别的一天(其实我妈并不赞同我今晚颓电脑，不过还是完成二月的任务吧)})\)

我不会告诉你上述做法有锅的

所以给你一组数据：戳我

使用中国剩余定理是有前提的，就是模数必须互质。

都错了，傻眼了吧（不要怀疑数据）

老祖宗太不认真了，

你不能这样质疑，因为他们发现并补救了：

拓展中国剩余定理

题目链接：P4777 【模板】扩展中国剩余定理（EXCRT）

看某大佬博客懵逼许久，终于在挑战程序设计竞赛（第2版）

找到了答案（当然我是在纸质书上看的）

比如说样例：

我们以先前的合并思想，对前两个合并：

样例：

\[\begin{cases}x\equiv6\pmod{11}\\x\equiv9\pmod{25}\\x\equiv17\pmod{33}\end{cases}
\]

对前两个：

\[\begin{cases}x\equiv6\pmod{11}\\x\equiv9\pmod{25}\end{cases}
\]

易得：

\[x=11t+6(t\in Z)
\]

带进去就万事大吉了：

\[11t+6\equiv9\pmod{25}
\]

化简

\[11t\equiv3\pmod{25}
\]

不得不说你该会解吧,易得：

\[t_{min}=23
\]

答案的处理

其实你会反代的对不对？

\[x=11×23+6=259\equiv259\pmod{lcm(11 ,25)=275}
\]

这样就好了，一一合并即可。

复杂度是\(O(n\log n)\),可以通过本题。

\(Code\):

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int MAXN=100005;

typedef long long ll;

inline long long mul(long long x,long long y,long long mod)

{

	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);

	return tmp<0 ? tmp+mod : tmp;

}

struct node

{

	ll n,m;//m是模数，n是余数

}a[MAXN];

ll x,y,ans=1;

void exgcd(ll a,ll b)

{

	if(b==0)

	{

		x=1,y=0;

		return;

	}

	exgcd(b,a%b);

	ll t=x;

	x=y;

	y=t-a/b*y;

}

ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

ll solve(ll a,ll b,ll c)

{

    ll g=gcd(a,b);

    if(c%g!=0) return -1;

    a/=g,b/=g,c/=g;

    exgcd(a,b);

    x=x*c;

    x=(x%b+b)%b;

    return x;

}

node merge(node x,node y)

{

	node ans;

	ans.m=(x.m/gcd(x.m,y.m))*y.m;

	ll t=solve(x.m,y.m,(y.n+y.m-x.n)%y.m);

	if(t<0)

	{

		ans.n=-1;

		return ans;

	}

	ans.n=mul(t,x.m,ans.m);

	ans.n=(ans.n+x.n)%ans.m;

	return ans;

}

ll n;

int main()

{

	scanf("%lld",&n);

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

	node rt=a[1];

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

	{

		rt=merge(rt,a[i]);

		if(rt.n<0)

		{

			printf("-1\n");

			return 0;

		}

	}

	printf("%lld\n",rt.n);

	return 0;

}

这个代码是会\(WA\)一个点被卡精度的的，不过大力快速乘（不懂大佬的方法）或是__int128并没什么意义，于是就......

巴特西

学习笔记：中国剩余定理（CRT）

引入

求解

\(Code\):

优化

\(Code\):

拓展中国剩余定理

答案的处理

\(Code\):

最新文章

热门文章