上节课我们讲了中国剩余定理的公式，公式忘了不要紧，OI WiKi 一下就可以了，我们这节课来讲一下中国剩余定理的推导，知其然知其所以然，而且讲完推导之后你会发现，其实我们不用再去背中国剩余定理了，对我们来说是很有好处的。

题目：给定 $2n$ 个整数 $a_1,a_2,…,a_n$ 和 $m_1,m_2,…,m_n$，求一个最小的非负整数 $x$，满足 $∀i∈[1,n],x≡m_i(\mod a_i)$。

P4777 【模板】扩展中国剩余定理（EXCRT）

这个式子很抽象，我们把它展开来看一下

这个题目没有任何限制，那么该怎么做呢？中国剩余定理要求 $m_1,m_2,...,m_n$ 之间要两两互质。那么当一个问题不满足于我们传统的经典思路时，就需要重新去考虑一下这个问题的推导过程，即当一个问题发生变化的时候，我们就需要重头把问题推导一遍，看一下需要在哪些地方做变形，这也就是为什么在讲算法的时候要把原理讲一遍，因为很有可能随着算法的普及，大家的水平越来越高，水涨船高的话，算法竞赛的难度也是越来越高，可能会对算法本身做一个改进，可能在竞赛的时候不光是把我们的板子套用过来就可以了，而是根据具体的问题对算法做一个调整，那么调整的话就一定要知道这个算法的原理是什么，不然的话就是随机乱试，错误的概论实在太大了。

那没有两两互质的限制的话我们就要考虑如何来做这个事？我们就要从原理来推导了，推导的过程我们也是秉持一个从易到难的原则，先考虑当我们有两个方程的时候，我们如何去求这个解，因为要满足 $n$ 个方程的话，就一定先满足前 $2$ 个方程，所以我们先从前 $2$ 个方程来考虑。

我们先把式子转化成一个等式，不然就不好做推导：

我们知道 $k_1,k_2$ 存在，但还不知道它们是多少，问题等价于给我们 $a_1,a_2,m_1,m_2$ 求 $k_1,k_2$，即用扩展欧几里得算法求系数 $k_1,k_2$ 的值。

()

假设我们已经求出来了 $k_1,k_2$，那么 $x=k_1*a_1+m_1$

然后上节课我们也讲过这是一个二元不定方程，不定方程的所有解是可以表现成这种形式的

这样我们前面加一个后面加一个就抵消了，这个就是我们不定方程的所有的解，其中 $k$ 是一个未知的整数，它都是我们的一组解。

因此 $x$ 的所有解就可以写成

那么我们要求的是最小非负整数解，那么我们先把所有的解的形式写出来，然后再想办法求一个最小的非负整数解。

我们继续整理就得到

$\frac{a_1a_2}{d}$ 也就是求 $a$ 和 $b$ 的最小公倍数 $[a_1,a_2]$，其中前面这一项是固定的，我们把它记为 $x_0$，后面这一项可以记为新的 $a$，所有我们再整理一下就是，$x$ 的所有解的形式为

然后我们可以惊奇的发现，这个式子和我们的 $x$ 的表达式是很像的

这个时候就可以把两个式子合并在一起，也就是说前两个方程需要满足的是这两个式子，然后我们通过刚才这一通推导，发现可以把它们变成一个式子对吧，然后这一个式子的形式是一样的。

所以我们可以通过这样的形式把两个不定方程合并成一个

那么我们一共有 $n$ 个方程，每次可以把两个方程合并成一个，那么我们合并 $n-1$ 次，就可以把这 $n$ 个方程（组）合并成一个方程

那当我们只有一个方程的时候，相求最小的非负整数 $x$ 就太简单了，相当于求一个

$x$ 的最小正整数解，其实就是求 $x_0\mod a$ 的正的余数，正的余数就取个余数就很简单。

所以说这就是我们这道题的一个思路，确实比较难，但是推导一遍就把我们前面讲的知识就串起来了，然后大家也可以看一下，一般竞赛的时候我们的数论题一般都是一个什么难度，大概就是这样，就是很少有那种直接用模板就可以算的，就可以直接把一个题目解决掉的一个情况，它不像我们的最短路问题，只要看出是最短路，然后把模板背一下，就可以过掉了，数论不一样，数论需要先把所有基础知识学一遍，然后再自己去做推导，推导之后根据这个推导的过程，把这个数论问题解决掉，其中解决掉的每一步都是需要用到我们前面讲的基础知识的，确实难度比较大，给大家一些时间，稍微整理一下。

因为题目比较复杂，所以我们一共讲两遍，第一遍我们用数学的方式来推导，第二个过程我们来展示一下代码的过程，怎么来实现一下这个代码。

数论题还是很麻烦的，因为还要考虑整数溢出的问题，然后我们把这一坨数学知识转换成代码，看一下怎么来实现它？

然后这个题它保证我们的数据范围在 $64$ 位范围内，需要用 long long 来存储，而且不需要写高精度，然后我们需要先把扩展欧几里得算法的模板背下来。背不出来也没关系，考试的时候可以现推，很快就可以推出来（在求 $gcd$ 的过程中顺便求出系数 $x,y$），

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


int main()
{

    return 0;
}

这个代码是我们上节课讲过的，忘记原理的同学可以看一下我们上节课的算法讲义，有整个推一遍。

$n$ 最多只有 $25$ 个方程（组），所以还是很少的，为什么方程组这么少呢？其实是有原因的，因为我们在把两个方程合并成一个方程的时候，我们会把 $a_1,a_2$ 变成 $[a_1,a_2]$，所以如果我们有 $n$ 个方程的话，最后我们所有的 $a$ 都会变成 $a_1,a_2,...,a_k$ 的最小公倍数，那么这个最小公倍数就太大了，就可能溢出我们整数范围了，因此我们的方程个数就不可能太多，太多的话我们的最小公倍数一定会特别的大。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


int main()
{
    int n;
    cin >> n;
	// 合并的思路是：每次把一个新的方程合并到一个现有方程中
    LL x = 0, a1, m1; // 假设我们现有方程是 a1,m1
    cin >> a1 >> m1;
    for (int i = 0; i < n - 1; i ++ )
    {
        LL a2, m2;
        cin >> a2 >> m2;
        // 然后开始合并 
        LL k1, k2; // 首先我们要求出来 k1 和 k2 的值 
        LL d = exgcd(a1, a2, k1, k2);
        // 然后这个方程有解的充要条件是： 
        if ((m2 - m1) % d)
        {
            x = -1;
            break;
        }
		// 如果有解的话，我们用扩展欧几里得求的其实是 k1a1-k2a2=d 的一个值
		// 然后我们要得到的是 m2-m1 的值，然后 m2-m1 是 d 的一个倍数
		// 所以我们要把等式两边同时翻若干倍，把 d 翻成 m2-m1 就可以了 
        k1 *= (m2 - m1) / d;
    	// 那么如果我们求出来一个k1的话，那么k1+k*(a2/d) 都是它的一组解
		// 然后这个题的话数据范围出的比较极限，就我们一定要让每次k都变得比较小
		// 否则的话中间结果会溢出，所以我们中间过程一定要让k变得比较小
		// 即把k1变成一个方程的最小的正整数解 
		
		// 那么我们先把 a2/d 先存下来
		LL t = a2 / d;
		// 然后把我们的k1变成一个最小的正整数解 
        k1 = (k1 % t + t) % t;

        x = k1 * a1 + m1;
		// 然后新的方程的 a 就等于 [a1,a2] 
		
		// 然后我们要把方程变成 x=x0+ka ， x=ka+m的形式，m就是m1 
		m1 = a1 * k1 + m1;
		
        a1 = abs(a1 / d * a2); // 求最小公倍数，负的正的都可以，我们这里取一个正的，方便一点 
        
		
    }
	// 结束之后如果有解的话我们输出它的最小正整数解 
    if (x != -1)
	{
		// 最小正整数解还需要对它做一个变形
		x = (m1 % a1 + a1) % a1; // 这里求的是 m1%a1正的余数
		// 因为c++在求余数的时候有个特点，求的不是数学意义上的余数 
	}
	
	cout << x << endl;

    return 0;
}

数学意义上的余数：

数学上余数 $-2$ 就是 $1$，但 c++会输出 $-2$，为了让它变成正数怎么办呢？就先把它模一下再加上 $3$ 再模一下，就会变成正数了，这是一个常用技巧。因为这样它的绝对值会到 $[0,3-1]$ 之内，$+3$ 之后一定会变成一个正数，然后再 $$ 就可以了。