裴蜀定理

内容

裴蜀定理，又称贝祖定理（Bézout's lemma）。

设 \(a,b\) 满足 \(\gcd(a,b) \mid c\)，则存在 \(x,y\) 使得 \(ax+by=c\) ，其中 \(a \in Z^*,b \in Z^*\)。

证明

显然有 \(\gcd(a,b) \mid a,\gcd(a,b) \mid b\) 。

因为 \(x,y \in Z^*\) ，

所以 \(\gcd(a,b) \mid ax,\gcd(a,b) \mid by\) 。

要使得 \(ax + by = c\) ，则 \(c\) 一定是 \(\gcd(a,b)\) 的倍数，

又有 \(a \in Z^*,b \in z^*\)，

则 \(\gcd(a,b) \mid c\)，

证毕。

应用

P4549 【模板】裴蜀定理

可由裴蜀定理计算两个数推广得来，对于本题的答案，我们只需不断求其中两个数的最大公约数，直到计算出所有数的最大公约数即为答案。

/*

Name: P4549 【模板】裴蜀定理

Solution: 裴蜀定理推广
   

By Frather_

*/
#include <iostream>
#include <cstdio>

using namespace std;
/*==================================================快读*/
inline int read()
{
    int X = 0, F = 1;
    char CH = getchar();
    while (CH < '0' || CH > '9')
    {
        if (CH == '-')
            F = -1;
        CH = getchar();
    }
    while (CH >= '0' && CH <= '9')
    {
        X = (X << 3) + (X << 1) + (CH ^ 48);
        CH = getchar();
    }
    return X * F;
}
/*===============================================定义变量*/
int n;
int x;
int ans;
/*=============================================自定义函数*/
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
/*=================================================主函数*/
signed main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        int tmp = read();
        x = tmp >= 0 ? tmp : -tmp;
        ans = gcd(ans, x);
    }
    printf("%d\n", ans);
    return 0;
}

中国剩余定理

『物不知数』问题

《孙子算法》

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
答曰：“二十三”。
术曰：三三数之剩二，置一百四十；五五数之剩三，置六十三，七七数之剩二，置三十，并之。得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五；一百六以上以一百五减之即得。

翻译：

一个整数除以3余2、除以5余3、除以7余2，求这个整数。
答案：23
解法：由于除以3余2，因此加上一个140；由于除以5余3，因此加上一个63；由于除以7余2，因此加上一个30；这三个数的和是140+63+30=233，再减去210，就得到了23了。

也就是说，

只要是除以 \(3\) 余了一个 \(1\) ，就加上一个 \(70\) ；
只要是除以 \(5\) 余了一个 \(1\) ，就加上一个 \(21\) ；
只要是除以 \(7\) 余了一个 \(1\) ，就加上一个 \(15\) 。

然后累加。超过了 \(106\) 就减去 \(105\) 就行了。

思想

求解如下同余方程组

\[\left\{ \begin{aligned} x & \equiv a_{1}\left(\bmod n_{1}\right) \\ x & \equiv a_{2}\left(\bmod n_{2}\right) \\ & \vdots \\ x & \equiv a_{k}\left(\bmod n_{k}\right) \end{aligned} \right. \]
其中 \(n_1,n_2,\cdots,n_k\) 两两互质。

计算所有模数的积 \(n\)
对于第 \(i\) 个方程:

a. 计算 \(m_{i}=\cfrac{n}{n_{j}}\);

b. 计算 \(m_{i}\) 在模 \(n_{i}\) 意义下的逆元 \(m_{i}^{-1}\);

c. 计算 \(c_{i}=m_{i} m_{i}^{-1}\)
方程組的唯一解为: \(a=\sum_{i=1}^{k} a_{i} c_{i}\pmod n\) 。

注意：执行 c. 时 不要对 \(n_{i}\) 取模

伪代码

n ← 1;
ans ← 0;
for i = 1 to k
    n ← n * n[i];

for i = 1 to k
{
    m ← n / n[i] b ← inv(m, n[i]); // b * m mod n[i] = 1
    ans ← (ans + a[i] * m * b) mod n;
}
return ans;

例题

『物不知数』问题

\(n=3\times 5\times 7=105\)；
三人同行七十希：

\[n_1=3,\\ m_1=n/n_1=35,\\ m_1^{-1}\equiv 2\pmod 3 \]
故

\[c_1=35\times 2=70 \]
五树梅花廿一支：

\[\begin{aligned} n_2 &=5,\\ m_2 &=n/n_2 \\ &=21,\\ m_2^{-1} &\equiv 1\pmod 5 \end{aligned} \]
故

\[\begin{aligned} c_2 &=21\times 1 \\ &=21 \end{aligned} \]
七子团圆正半月：\

\[\begin{aligned} n_3 &=7,\\ m_3 &=n/n_3\\ &=15,\\ m_3^{-1} &\equiv 1\pmod 7 \end{aligned} \]
故

\[\begin{aligned} c_3 &=15\times 1 \\ &=15 \end{aligned} \]
所以方程组的唯一解为

除 百零五 得

\[\begin{aligned} a &\equiv 2\times 70+3\times 21+2\times 15\\ &\equiv 233\\ &\equiv 23 \pmod {105} \end{aligned} \]

P1495 【模板】中国剩余定理(CRT)/曹冲养猪

/*

Name: P1495 【模板】中国剩余定理(CRT)/曹冲养猪

Solution: 中国剩余定理
   

By Frather_

*/
#include <iostream>
#include <cstdio>
#include <algorithm>

#define int long long

using namespace std;
/*==================================================快读*/
inline int read()
{
    int X = 0, F = 1;
    char CH = getchar();
    while (CH < '0' || CH > '9')
    {
        if (CH == '-')
            F = -1;
        CH = getchar();
    }
    while (CH >= '0' && CH <= '9')
    {
        X = (X << 3) + (X << 1) + (CH ^ 48);
        CH = getchar();
    }
    return X * F;
}
/*===============================================定义变量*/
int n;

const int _ = 1000010;

int a[_], m[_];
int p = 1;
int m_[_];
int x, y;

int ans;
/*=============================================自定义函数*/
void ex_gcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return;
    }
    ex_gcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - y * (a / b);
}
/*=================================================主函数*/
signed main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        m[i] = read();
        p *= m[i];
        a[i] = read();
    }
    for (int i = 1; i <= n; i++)
    {
        m_[i] = p / m[i];
        x = 0;
        y = 0;
        ex_gcd(m_[i], m[i], x, y);
        ans += a[i] * m_[i] * (x >= 0 ? x : x + m[i]);
    }
    printf("%lld\n", ans % p);
    return 0;
}

P2480 [SDOI2010]古代猪文

暂时稍微放一下吧。。