本文已经重置！新的文章在下方链接

(注意，新文章为课程论文，相较于原文在严谨性和代码可读性，规范性方面有了较大的改进，但是也相对枯燥，请酌情选择！)

链接1（PDF下载）：https://files.cnblogs.com/files/ztz11/PDF%E7%89%88.rar?t=1732165734&download=true

（请将链接复制到地址栏，直接点击链接会导致下载错误）

链接2（图片版博客）

前置知识

1.

a%b=d,c%b=e,

则(a+c)%b=(d+e)%b(正确性在此不加证明)

2.

a%b=1,则（d $\times$ a）%b=d%b(正确性在此不加证明)

下面先看一道题（改编自曹冲养猪）：

烤绿鸟的故事

题目描述：

mian包是一个贪吃的孩子，这天，他买了一堆绿鸟吃。当然他的妈妈并不想让他吃太多食物（~~因为那样会发胖~~），为了避免老妈的唠叨，他决定不告诉他的妈妈绿鸟数量，而是将绿鸟的数量x用以下式子来描述

注： $≡$ 为同余符号

\begin{cases}x≡b_1 (mod a_1)\\x≡b_2 (mod a_2)\\...\\x≡b_n (mod a_n)\end{cases}

（

a_1

a_2

......

a_n

两两互质）
由于他的妈妈数学不好，于是就来向你求助了，请你求出mian包最少买了多少烤绿鸟

输入输出格式

输入格式：

第一行包含一个整数n (n <= 10) – 告诉妈妈的式子数，接下来n行，每行两个整数ai, bi( bi <= ai <= 1000)

首先，我们把这道题简化成下面的图

样例为：

CPP

很显眼吧？怎么做呢？

1.妈妈，我会暴力

这就很简单了

我们从第二个开始枚举

初始值为a1+b1；

每次自加当前的已经满z足的

a_1 \times a_2\times......\times

a_{i-1}$ 的乘积（为什么我接下来说）

如果当前值已经满足

%a_i

b_i

则当前已经成立

ps：上式为什么成立呢？

以上面的例子为例，看下面我的图

当已经满足前两个等式时，我们增加

a_1 \times a_2

那么我们会增加15只绿鸟

看图：

很显然，15%3=0，15%5=0

所以增加15的话一定满足当前的等式

自然，暴力就解决了

暴力代码：

CPP

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a,b,c,d,e,f,g,kkk,n;
struct zzzz{
    int x,y,z;
}ltt[15];
bool cmp(zzzz s,zzzz t)
{
    return s.x>t.x;
}
int main()
{
    cin>>n;
    kkk=1;
    for(a=1;a<=n;a++)
    {
        cin>>ltt[a].x>>ltt[a].y;
    }
    sort(ltt+1,ltt+n+1,cmp);
    kkk=ltt[1].x;
    g=ltt[1].y;
    f+=2;
    while(f<=n)//枚举每个等式
    {
        while(1)
        {
            if(g%ltt[f].x==ltt[f].y)
            {
                kkk=kkk*ltt[f].x;
                f++;
                break;
            }
            g=g+kkk;//自加，直到满足当前等式
        }
    }
    cout<<g;
}

诚然，这种方法好想也好写，但是，我们要注意一个问题

看下面这个式子：

\begin{cases}x≡1 (mod 3)\\x≡1 (mod 5)\\x≡19260817 (mod 1000000007)\end{cases}

好吧，你自加去吧，保证TLE

这时，我们就需要一个高效的算法

前置知识3：

每一个crt方程组的解在模

a_1 \times a_2 \times …… \times a_n

意义下有且只有1个

为什么呢？因为每个解之间的差是所有a的乘积，加数不管对序列中的哪个数取模都是0呗

2.关于暴力的扩展

先说点别的东西

由上面的暴力我们可以看出，该样例crt解法的本质是从5和7的公倍数中找一个除以3余1的数

n_1

，从3和7的公倍数中找一个除以5余1的数

n_2

，从3和5的公倍数中找一个除以7余2的数

n_3

，再将三个数相加得到解。

那么我们可不可以说，更多项的答案也可以这样的得来吗？

答案是肯定的

我们设{

a_1 \times a_2 \times ...... \times a_n

}为mul

然后按照暴力的方法，我们可以得到这样一个式子：

k_1\times\frac{(mul)}{a1}

k_2\times\frac{(mul)}{a2}

+……+

k_n\times\frac{(mul)}{an}

并满足(

k_i\times\frac{(mul)}{a_i}

a_i

b_i

)

正确性？看下面：

首先，因为

a_i

两两互质，所以我们可以知道，

\frac{(mul)}{a_i}

一定不是

a_i

的倍数

而

\frac{(mul)}{a_j}

\ne

i)一定是

{a_i}

的倍数

所以，我们知道上式中除了第

i

项其他所有项 ≡ 0（mod

{a_i}

）

所以，原式 ≡

k_i\times\frac{(mul)}{a_i}

(mod

a_i

)

然后，我们又根据一开始那个式子的约束条件，得出

k_i\times\frac{(mul)}{a_i}

a_i

b_i

所以，整个式子满足对

a_i

的约束条件

我们将这个推广开来，即可证得原式是crt方程组的一个解

然后根据前置知识三，即求得原始的最小解

你说了这么多，但该怎么实现呢？

我们设

\frac{mul}{a_i}

为

m_i

那么，原式就变成了：

k_1 \times m_1 + k_2 \times m_2+......+k_n \times m_n

且

k_i \times m_i

≡

b_i

(mod

a_i

)

** 这是什么？**

很多人表示一脸懵逼，不知道该怎么求？？？

好，让我们仔细看一下

我们由前置定理2可得：

如果

k\times m_i

≡ 1 (mod

a_i

)

那么当

k_i=b_i \times k

时

k_i \times m_i

≡

b_i

(mod

a_i

)

那么怎么求

k

呢？

我们知道有一个东西叫逆元。。

什么是逆元？

请出门左转以前的一篇日报

浅谈模质数意义下的乘法逆元

这里，我们就可以用逆元来解k咯

代码里我用的是exgcd哦

代码是重点：

CPP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
#define int long long
using namespace std;
int a[15],b[15],n;
void exgcd(int a,int b,int &ls,int &x,int &y)//求逆元
{
    if(b==0)
	{
        ls=a;
        x=1;
		y=0;
    }
    else
	{
        exgcd(b,a%b,ls,y,x);
        y-=(a/b)*x;
    }
}
signed main()
{
	int mod=1,ls,y,x=0;
    scanf("%lld",&n);
    for(rii=1;i<=n;i++)
    {
		scanf("%lld%lld",&a[i],&b[i]);  	
    }
    for(rii=1;i<=n;i++)
	{
		mod*=a[i];
	}
    for(rii=1;i<=n;i++)
	{
        int kkk=mod/a[i];
        exgcd(a[i],kkk,ls,ls,y);
        x=(x+y*kkk*b[i])%mod;
    }
	int ans=(x+mod)%mod;
    printf("%lld",ans);
}

毒瘤 Imagine（模板excrt出题人）：我的 $a_i$ 不互质！

好吧，我们进入下一步，

excrt

~~难的不是一点半点,好像和上一个已经没什么关系了~~

因为大家注意一点，上面理论的基础是

a_i

互质

那么这里这里不互质了我们怎么办呢？

（说暴力的站墙角）

但我们又没有好的解法......

看来，我们不得不学着暴力两两合并了

当然，我们不能像暴力一样通过自加两两合并

我们要用一个好玩的东西——

exgcd

对于原方程的两个式子，我们可以化成这样（请跟着我的公式）：

\begin{cases}x≡b_1 (mod a_1)\\x≡b_2 (mod a_2)\end{cases}

则

a_1 \times y+b_1=a_2 \times z+b_2

这就是一眼看穿的问题了

所以，这里就能用上面exgcd了

顺次两两合并

每次得出一个当前的解

合并很简单，

我们首先利用exgcd求出一个解

然后利用这个解，新构建一个新的方程带入计算

怎么构建新的解呢？

我们目前有两个方程，一个是由前面的方程合并来的，我们称它为方程1

另一个是我们这一步要合并的方程，称为方程2

\begin{cases}x≡b (mod a)---1\\x≡b_i (mod a_i)---2\end{cases}

我们利用

exgcd

可以求出这里的x

现在的关键就在于如何合并

a

和

a_i

我们知道，

x

lcm

（

a

a_i

）仍然满足上面的这个方程组

（因为

lcm

（

a

a_i

）%

a

=0,

lcm

（

a

a_i

）%

a_i

=0）

我们就可以得出一个新的方程了

代码：

CPP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
#define int long long
using namespace std;
int a[100005],b[100005],n,cj,ans,mod;
int exgcd(int a,int b,int &x,int &y)
{	
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,x,y);
    int zcq=x;
    x=y;
    y=zcq-a/b*y;
    return gcd;
}
int pw(int l,int r,int p)
{
    int an=0;
    while(r>0)
    {
        if(r&1)
        {
            an=(an+l)%p;
        }
        l*=2;
        l%=p;
        r/=2;
    }
    return an;
}
signed main()
{
    scanf("%lld",&n);
    for(rii=1;i<=n;i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
    }
    cj=a[1];
    ans=b[1];
    int x,y;
    for(rii=2;i<=n;i++)
    {
        int zcq=cj;
        int st=a[i];
        int ltt=(b[i]-ans%st+st)%st;
        int gys=exgcd(zcq,st,x,y);//求解
        int kkk=st/gys;
        x=pw(x,ltt/gys,kkk);
        ans+=cj*x;
        cj*=kkk;
        ans+=cj;
        ans%=cj;//防溢出（同时确保答案最小）
    }
    cout<<ans;
    //注意：此处已忽略乘法溢出（不用快速乘）
}

会了后别忘了写NOI2018屠龙勇士哦~

特别感谢luogu曹冲养猪和excrt题解作者，他们给了我很多思路

如果出锅，请私信联系（评论我不一定看的到），万分感谢

统一回复关于Latex爆炸的问题：

Latex在后台的预览中是正常的

但是在主界面就炸了

我也不知道为啥[苦笑]

有时间我会试着用图片代替掉Latex的

向大家说声抱歉了

浅析中国剩余定理（从CRT到EXCRT））

文章操作

本文已经重置！新的文章在下方链接

(注意，新文章为课程论文，相较于原文在严谨性和代码可读性，规范性方面有了较大的改进，但是也相对枯燥，请酌情选择！)

前置知识

1.

2.

下面先看一道题（改编自曹冲养猪）：

烤绿鸟的故事

题目描述：

输入输出格式

输入格式：

1.妈妈，我会暴力

暴力代码：

诚然，这种方法好想也好写，但是，我们要注意一个问题

前置知识3：

2.关于暴力的扩展

那么我们可不可以说，更多项的答案也可以这样的得来吗？

答案是肯定的

正确性？看下面：

你说了这么多，但该怎么实现呢？

代码是重点：

毒瘤 Imagine（模板excrt出题人）：我的 $a_i$ 不互质！

excrt

难的不是一点半点,好像和上一个已经没什么关系了

（说暴力的站墙角）

代码：

如果出锅，请私信联系（评论我不一定看的到），万分感谢

统一回复关于Latex爆炸的问题：

相关推荐

评论

浅析中国剩余定理（从CRT到EXCRT））

文章操作

本文已经重置！新的文章在下方链接

(注意，新文章为课程论文，相较于原文在严谨性和代码可读性，规范性方面有了较大的改进，但是也相对枯燥，请酌情选择！)

前置知识

1.

2.

下面先看一道题（改编自曹冲养猪）：

烤绿鸟的故事

题目描述：

输入输出格式

输入格式：

1.妈妈，我会暴力

暴力代码：

诚然，这种方法好想也好写，但是，我们要注意一个问题

前置知识3：

2.关于暴力的扩展

那么我们可不可以说，更多项的答案也可以这样的得来吗？

答案是肯定的

正确性？看下面：

你说了这么多，但该怎么实现呢？

代码是重点：

毒瘤 Imagine（模板excrt出题人）：我的aia_iai​不互质！

excrt

难的不是一点半点,好像和上一个已经没什么关系了

（说暴力的站墙角）

代码：

如果出锅，请私信联系（评论我不一定看的到），万分感谢

统一回复关于Latex爆炸的问题：

相关推荐

评论

毒瘤 Imagine（模板excrt出题人）：我的 $a_i$ 不互质！