数学 - 同余

拓展欧几里得算法

裴蜀定理：对于任意正整数 $a,b$ 一定存在非零整数 $x,y$ 使 $ax+by=\gcd(a,b)$

如果已知：

$$by+(a\text{ mod }b)x=d\\$$

则能递推出：

$$\begin{aligned} by+(a-\lfloor\frac{a}{b}\rfloor b)x&=d\\ ax+b(y-\lfloor\frac{a}{b}\rfloor x)&=d\\ \end{aligned}$$

然后就写出 exgcd 算法求一组解了。

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

由于 $ax_0+by_0=d$，那么满足条件的所有 $x,y$ 一定也满足：

$$a(x+\frac{b}{d})+b(y-\frac{a}{d})=d$$

也就有通解如下：

$$\left \{ \begin{aligned} x&=x_0+k\frac{b}{d}\\ y&=y_0-k\frac{a}{d}\\ k&\in \Z \end{aligned}\right .$$

除以 $d$ 后这个数仍为整数。

中国剩余定理

求解下列一阶线性同余方程组：

$$\left \{\begin{aligned} x&\equiv a_1(\text{mod }m_1)\\ x&\equiv a_2(\text{mod }m_2)\\ &\vdots\\ x&\equiv a_k(\text{mod }m_k) \end{aligned}\right .$$

方程组的解是：

$$x=\sum_{i=1}^ka_iM_iM_i^{-1}+nM,n\in\Z\\ M=\prod _{i=1}^k m_i,M_i=\frac{M}{m_i},M_i^{-1}(\text{mod }m_i)$$

对于方程 $x\equiv a_i(\text{mod }m_i)$ 来说，除了 $a_iM_iM_i^{-1}$ 模 $m_i$ 为 $a_i$，其余项都为 $0$，因此这个解是正确的。

对于求 $M_i^{-1}$ 可以用拓展欧几里得算法，等价于求解下列方程：

$$M_iM_i^{-1}\equiv 1(\text{mod }m_i)\\ M_iM_i^{-1}-km_i=1$$

其中 $M_i,m_i$ 是已知量。

好四和好五

求关于 $x,y$ 的方程 $4x+5y=n$ 的非负整数解的个数。

题目链接：AcWing 5181。

根据裴蜀定理和 exgcd 算法，我们知道 $4x+5y=1$ 的所有解可以表示为：

$$x=-1+5k, y=1-4k$$

所以方程 $4x+5y=n$ 的所有解就是：

$$x=-n+5k, y=n-4k$$

我们将题目给的方程看作一条直线方程，那么它与 $x,y$ 轴的交点分别是 $(\frac{n}{4},0),(0,\frac{n}{5})$。

从 $x$ 的角度看，我们可以推出 $\frac{n}{5}\le k\le \frac{n}{4}$，从 $y$ 看亦然，所以答案就是下面的式子：

$$\lfloor\frac{n}{4}\rfloor-\lceil \frac{n}{5}\rceil+1=\lfloor\frac{n}{4}\rfloor-\lfloor\frac{n+4}{5}\rfloor+1$$

这样把枚举的 $O(n)$ 优化到了 $O(1)$，还是可以的。

#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", n/4-(n+4)/5+1);
    return 0;
}

同余方程

求同余方程 $ax\equiv 1(\text{mod }b)$ 的最小整数解，数据保证一定有解。

题目链接：AcWing 203。

方程等价变形：

$$ax=mb+1\\ ax-bm=1$$

已知 $a, b$ 求一组 $x,m$ 拓展欧几里得。

#include <iostream>
using namespace std;

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

int main() {
    int a, b, x, m;
    cin >> a >> b;
    int d = exgcd(a, b, x, m), k = b/d;
    // 写 (x%k+k)%k 可能爆 int
    x %= k;
    if (x < 0) x += k;
    cout << x << endl;
    return 0;
}

最幸运的数字

现在给定一个正整数 L，请问至少多少个 8 连在一起组成的正整数是 L 的倍数。

题目链接：AcWing 202。

1. 推导公式。

   对于 $x$ 个 $8$ 连在一起组成的正整数，应该是：

   $$\sum_{i=0}^{x-1} (8\times10^i)$$

   这就是一个等比数列的求和公式了，首项为 $8$，公比为 $10$ 的前 $x$ 项和：

   $$S_n=\frac{8(1-10^{x})}{1-10}=\frac{8(10^{x}-1)}{9}$$

   也就是问 $x$ 最小为多少可以使得：

   $$\begin{aligned} L&|\frac{8(10^x-1)}{9}\\ 9L&|8(10^x-1)\\ C&|(10^x-1)\\ 10^x&\equiv 1(\text{mod }C),C=\frac{9L}{\gcd(L,8)} \end{aligned}$$

   其中第三步，由于 $8,9$ 互质，于是 $\gcd(9L,8)=\gcd(L,8)$，两边除掉这个数字的时候， $\cfrac{8}{\gcd(L,8)}$ 中就和左边没有任何一个公约数了。

2. 求最小值。

   若 $x\gt 0$，必须保证 $10^x,C$ 互质，否则这个同余式不可能成立。

   由欧拉定理得：

   $$10^{\varphi(C)}\equiv1(\text{mod } C)$$

   但 $\varphi(C)$ 不一定是最小使此方程成立的数，若 $x$ 是最小的数，一定有 $x|\varphi(C)$，下面用反证法证明：

3. 证明性质。

   若存在 $x$ 使得 $\varphi(C)=qx+r(0<r<x)$，那么：

   $$\begin{aligned} 10^{qx+r} &\equiv 1(\text{mod }C)\\ \Rightarrow 10^{r}&\equiv 1(\text{mod }C)\\ \end{aligned}$$

   因为 $10^x\equiv 1$ 所以 $10^{qx}\equiv 1$，这个用二项式展开就可以说明 $(kC+1)^q$ 除了 $C_q^q 1^q=1$ 这项之外其余任意项都含有 $C$，也就可以被除掉。

   因此 $x|\varphi(C)$ 成立。

那么目标就是看 $10,C$ 是否互质，如果互质找到最小的 $x|\varphi(C)$，并输出。

这个题还有一个比较坑的地方，它快速幂会爆 long long，这里用龟速乘防止爆，因为全都是 long long 直接宏替换得了。

#include <cstdio>
#include <algorithm>
using namespace std;

#define int long long

int qmul(int a, int k, int p) {
    int res = 0;
    while (k) {
        if (k & 1) res = (res + a) % p;
        a = (a+a) % p;
        k >>= 1;
    }
    return res;
}

int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = qmul(res, a, p);
        a = qmul(a, a, p);
        k >>= 1;
    }
    return res;
}

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

int euler(int c) {
    int res = c;
    for (int i = 2; i <= c/i; i++) {
        if (c % i == 0) {
            res -= res/i;
            while (c % i == 0) c /= i;
        }
    }
    if (c > 1) res -= res/c;
    return res;
}

int solve(int l) {
    int c = 9*l/gcd(8, l);
    if (c % 2 == 0 || c % 5 == 0) return 0;
    
    int phi = euler(c);
    int res = 1e18;
    for (int i = 1; i <= phi/i; i++) {
        if (phi % i == 0) {
            // 从小到大找到的一定是最小
            if (qmi(10, i, c) == 1) return i;
            if (qmi(10, phi/i, c) == 1) res = min(res, phi/i);
        }
    }
    return res;
}

signed main() {
    int l;
    signed t = 0;
    while (scanf("%lld", &l), l) {
        printf("Case %d: %lld\n", ++t, solve(l));
    }
    return 0;
}

曹冲养猪

第一行包含一个整数 n —— 建立猪圈的次数，接下来 n 行，每行两个整数 ai, bi，表示建立了 ai 个猪圈，有 bi 头猪没有去处，即 $x\equiv b_i(\text{mod }a_i)$。你可以假定 a1~an 互质。

题目链接：AcWing 1298，P1495。

中国剩余定理的裸题。

#include <cstdio>
using namespace std;

typedef long long LL;
const int N = 15;
LL a[N], b[N];

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, y, x);
    y -= a/b*x;
    return d;
}

int main() {
    int n;
    
    scanf("%d", &n);
    LL M = 1;
    for (int i = 0; i < n; i++) {
        scanf("%lld%lld", &a[i], &b[i]);
        M *= a[i];
    }
    
    LL res = 0;
    for (int i = 0; i < n; i++) {
        LL Mi = M / a[i];
        // Mi*t = ka[i] + 1
        // Mi*t-ka[i]=1
        LL t, k;
        exgcd(Mi, a[i], t, k);
        res += Mi*t*b[i];
    }
    res %= M;
    if (res < 0) res += M;
    printf("%lld\n", res);
    return 0;
}