阅读数 nan

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

$有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？$

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。
　　　　　　 　　　　　　　　　　　　　　　　　　　　 　　　　　———摘自教练的PPT

$\text{crt}$

中国剩余定理(crt),即让你求解一个关于 $x$ 的同余方程：​

$x\equiv a_1 \pmod{m_1}$

$x\equiv a_2 \pmod{m_2}$

$…$

$x\equiv a_n \pmod{m_n}$

且保证 ${ m_1,m_2…m_n }$ 两两互质。

---

我们先考虑一个例子：

$x\equiv 2\pmod{3}$

$x\equiv 3\pmod{5}$

$x\equiv 4\pmod{7}$

如果用小奥方法，就是将 $x=2$ 不断地加 $3$,发现当 $x=8$ 时同时满足第二个式子,然后不停地加 $\operatorname{lcm}(3,5)$，当 $x=53$ 时发现全部满足。

我们知道 $a,b,c…| \operatorname{lcm}(a,b,c…)$

所以我们定义 $M_1=\operatorname{lcm}(5,7),M_2=\operatorname{lcm}(3,7),M_3=\operatorname{lcm}(3,5)$

对于第①个式子,我们只需要满足 $t_1M_1\equiv 2 \pmod{m_1}$ ；

对于第②个式子,我们只需要满足 $t_2M_2\equiv 3 \pmod{m_2}$ ；

对于第③个式子,我们只需要满足 $t_3M_3\equiv 4 \pmod{m_3}$ 。

发现可以用 $\operatorname{exgcd}$ 求关于 $t_i$ 的同余方程 $t_iM_i\equiv 1 \pmod{m_i}$ 的最小正整数解

---

那么最终的答案公式应为:

$$(t_1M_1a_1+t_2M_2a_2+…+t_nM_na_n)%\operatorname{lcm(m_1,m_2,…,m_n)}$$

代码实现

#include <cstdio>
using namespace std;
typedef long long LL;
LL n,a[20],m[20],M[20],ans,lcm=1;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    LL x1,y1;
    LL ans=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-a/b*y1;
    return ans;
}

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&m[i]),lcm*=a[i];
    for(int i=1;i<=n;i++)
    {
        LL x=0,y=0,total=1;
        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;
            total*=a[j];
        }
        M[i]=total;
        exgcd(M[i],a[i],x,y);
        x=(x%a[i]+a[i])%a[i];
        ans=(ans+x*M[i]*m[i])%lcm;
    }
    printf("%lld\n",ans);
    return 0;
}

$\text{excrt}$

$\text{excrt}$ 与 $\text{crt}$ 唯一的区别是 $m_i$ 是否两两互质。

考虑去解决其中的两个方程：

$$\begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \end{cases}$$

其中 $\gcd(m_1,m_2)$ 不一定为 $1$。

考虑转化，将式子改写为：

$$\begin{cases} x=k_1m_1+a_1 \ x=k_2m_2+a_2\end{cases}$$

$$\Rightarrow k_1m_1-k_2m_2=a_2-a_1$$

这是二元一次方程基本形式，使用 $\text{exgcd}$ 解决，注意若 $a_2-a_1$ 不为 $\gcd(m_1,m_2)$ 的倍数时无解。

然后我们找到一个满足上述方程的解集中 $k_1$ 的最小非负整数解，然后代入至 $x=k_1m_1+a_1$ 求出 $x$，此时 $x$ 对两个方程同时满足，记得出的值为 $x’$。

那么我们可以将这两个方程合并为一个方程：$x\equiv x’ \pmod{\operatorname{lcm}(m_1,m_2)}$。

以此类推合并完所有方程就可以求出最终的答案。

代码实现

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

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;

const int Inf = 0x3f3f3f3f;
const ll Lnf = 0x3f3f3f3f3f3f3fll;
const int Mod = 1000000007;
const int maxn = 100005;
int n;
bool f = true;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll z = x;
    x = y, y = z - y * (a / b);
    return d;
}

ll mul(ll a, ll b, ll p) {
    a %= p, b %= p;
    ll c = (lf)a * b / p;
    return (a * b - c * p + p) % p;
}

void solve(ll &m, ll &a, ll tm, ll ta) {
    ll k, tk, g = exgcd(m, tm, k, tk), lcm = m / g * tm;
    if((a - ta) % g != 0) {
        f = false;
        return;
    }
    k = mul(k, (ta - a) / g, tm / g);
    a = (mul(k, m, lcm) + a) % lcm;
    m = lcm;
    if(a < 0) {
        a += m;
    }
}

void excrt() {
    ll a = 0, m = 1, ta, tm;
    for(int i = 1;i <= n;i++) {
        scanf("%lld%lld", &tm, &ta);
        solve(m, a, tm, ta);
        if(f == false) {
            puts("-1");
            return;
        }
    }
    printf("%lld\n", a);
}

int main() {
    scanf("%d", &n);
    excrt();
    return 0;
}