标签：gcd 数论 笔记 pmod int varphi left 同余 equiv

目录

• 同余
  • 带余数除法
    • 带余数除法的定义与基本性质
    • 模运算加速算法
      • 模运算封装
      • 龟速乘
      • 快速幂
      • 矩阵快速幂
  • 同余的定义与基本性质
  • 同余类与剩余系的定义与基本性质
  • 欧拉函数
    • 欧拉函数的定义与基本性质
    • 欧拉函数的求法
      • 试除法
      • 线性筛求欧拉函数
    • 欧拉函数的其他性质
  • 同余重要定理
    • 费马小定理
    • 欧拉定理
    • 威尔逊定理
  • 二元一次不定方程
    • 二元一次不定方程的定义与基本性质
    • 裴蜀定理
    • 解二元一次不定方程
      • 扩展欧几里得算法
    • 二元一次不定方程的非负整数解
  • 乘法逆元
    • 乘法逆元的定义与基本性质
    • 乘法逆元的求法
      • 费马小定理法
      • 扩展欧几里得算法
      • 线性递推求乘法逆元
      • 线性递推求阶乘逆元
  • 一元一次同余方程
    • 一元一次同余方程的定义与基本性质
    • 解一元一次同余方程
      • 扩展欧几里得算法
  • 一元一次同余方程组
    • 一元一次同余方程组的定义与基本性质
    • 中国剩余定理（孙子定理）
    • 解一元一次同余方程组
      • 中国剩余定理
      • 扩展中国剩余定理
  • 特殊求和问题
    • 问题描述
    • 求解方式
      • 类欧几里得算法

同余

带余数除法

带余数除法的定义与基本性质

定义 对于整数 \(a,b\) 且 \(b \neq 0\) ，一定存在整数 \(q,r\) 满足 \(a = qb + r\) ，其中 \(r \in [0,b)\) ，称 \(q\) 为 \(a\) 除以 \(b\) 的商， \(r\) 为 \(a\) 除以 \(b\) 的余数。

注意，c++的 % 模运算指定 \(r\) 和 \(a\) 同号， / 整除运算指定正数取下整、负数取上整，都需要辨别。

模运算的定义 \(a \bmod b\) 的结果为 \(a\) 除以 \(b\) 的余数 \(r\) ，运算优先级同乘除。

模 \(m\) 加法 \((a+b) \bmod m\) 。

模 \(m\) 减法 \((a-b) \bmod m\) 。

模 \(m\) 乘法 \(ab \bmod m\) 。

性质1 模运算与整除的关系

\[\begin{cases} a - b\cdot \left\lfloor \dfrac{a}{b} \right\rfloor &, b > 0\\ a - b\cdot \left\lceil \dfrac{a}{b} \right\rceil &, b < 0 \\ \end{cases} \]

性质2 模运算的运算规律

\[\begin{aligned} a \bmod m \pm b \bmod m &= (a\pm b) \bmod m\\ (a \bmod m) \cdot (b \bmod m) &= ab \bmod m\\ (a \bmod m)^k &= a^k \bmod m,k\in \N \end{aligned} \]

性质3 \(a \bmod n = a\bmod m = x\) 且 \(\gcd(n,m) = 1\) ，则 \(a \bmod nm = x\)

性质3的证明：

由同余式可得 \(a - x = k_1n = k_2m\) ，又 \(\gcd(n,m) = 1\) ，根据整除基本性质4，所以 \(m \mid k_1n \iff m \mid k_1\) ，所以设 \(k_1 = k_3m\) ，于是 \(a-x = k_3mn\) ，即 \(a \bmod nm = x\) 。

模运算加速算法

模运算封装

非正式赛强大模板，告别打 % 打到手酸。

正式赛斟酌使用。

时间复杂度

1. 求幂 \(O(\log k)\)
2. 逆元 \(O(\log P)\)
3. 其余 \(O(1)\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;
struct Modint {
    int val;
    Modint(int _val = 0):val(_val %P) { format(); }
    Modint(ll _val):val(_val %P) { format(); }

    //if val in [-P,2P)
    //maybe slower than global version
    Modint &format() {
        if (val < 0) val += P;
        if (val >= P) val -= P;
        return *this;
    }
    Modint inv()const { return qpow(*this, P - 2); }

    Modint &operator+=(const Modint &x) { val += x.val;return format(); }
    Modint &operator-=(const Modint &x) { val -= x.val;return format(); }
    Modint &operator*=(const Modint &x) { val = 1LL * val * x.val % P;return *this; }
    Modint &operator/=(const Modint &x) { return *this *= x.inv(); }
    friend Modint operator-(const Modint &x) { return { -x.val }; }
    friend Modint operator+(Modint a, const Modint &b) { return a += b; }
    friend Modint operator-(Modint a, const Modint &b) { return a -= b; }
    friend Modint operator*(Modint a, const Modint &b) { return a *= b; }
    friend Modint operator/(Modint a, const Modint &b) { return a /= b; }

    friend Modint qpow(Modint a, ll k) {
        Modint ans = 1;
        while (k) {
            if (k & 1) ans = ans * a;
            k >>= 1;
            a = a * a;
        }
        return ans;
    }

    friend istream &operator>>(istream &is, Modint &x) {
        ll _x;
        is >> _x;
        x = { _x };
        return is;
    }
    friend ostream &operator<<(ostream &os, const Modint &x) { return os << x.val; }
};

龟速乘

用于可能爆 long long 数字的乘法取余。

不过一般可以用 __int128 替代了。

时间复杂度 \(O(\log b)\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;
ll qmul(ll a, ll b) {
    ll ans = 0;
    while (b) {
        if (b & 1) ans = (ans + a) % P;
        b >>= 1;
        a = (a << 1) % P;
    }
    return ans;
}

快速幂

幂取余，\(a\) 越大速度越慢。

时间复杂度 \(O(\log k)\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;
int qpow(int a, ll k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = 1LL * ans * a % P;
        k >>= 1;
        a = 1LL * a * a % P;
    }
    return ans;
}

矩阵快速幂

矩阵幂取余。

时间复杂度 \(O(n^3 \log k)\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;
struct Matrix {
    int n, m;
    vector<vector<int>> mat;

    explicit Matrix(int _n):n(_n), m(_n), mat(_n + 1, vector<int>(_n + 1)) {
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++)
                mat[i][j] = i == j;
    }
    Matrix(int _n, int _m):n(_n), m(_m), mat(_n + 1, vector<int>(_m + 1)) {}

    friend Matrix operator*(const Matrix &A, const Matrix &B) {
        Matrix ans(A.n, B.m);
        if (A.m != B.n) return ans;
        for (int i = 1;i <= A.n;i++)
            for (int j = 1;j <= B.m;j++)
                for (int k = 1;k <= A.m;k++) //a.m == b.n
                    ans.mat[i][j] = (ans.mat[i][j] + 1LL * A.mat[i][k] * B.mat[k][j]) % P;
        return ans;
    }
    friend Matrix operator^(Matrix A, ll k) {
        Matrix ans(A.n);
        while (k) {
            if (k & 1) ans = ans * A;
            k >>= 1;
            A = A * A;
        }
        return ans;
    }

    friend ostream &operator<<(ostream &os, const Matrix &A) {
        for (int i = 1; i <= A.n; i++)
            for (int j = 1; j <= A.m; j++)
                os << A.mat[i][j] << " \n"[i != A.n && j == A.m];
        return os;
    }
};

同余的定义与基本性质

定义 若整数 \(a,b\) 模 \(m\) 的余数相等，则称 \(a,b\) 模 \(m\) 同余，记作 \(a \equiv b \pmod m\) 。若余数不等，则称 \(a,b\) 模 \(m\) 不同余，记作 \(a \not \equiv b \pmod m\) 。

约定 由于对负模数 \(m\) 的讨论等价于正模数的讨论，所以若不特殊指明，我们假定模数 \(m>0\) 。

性质1（自反性） \(a \equiv a \pmod m\) 。

性质2（对称性） \(a\equiv b \pmod m \iff b \equiv a \pmod m\) 。

性质3（传递性） \(a \equiv b \pmod m \text{ 且 } b \equiv c \pmod m \Rightarrow a \equiv c \pmod m\) 。

性质4（同加性）

\[\begin{aligned} a \equiv b \pmod m &\iff a \pm c \equiv b \pm c \pmod m\\ a \equiv b \pmod m,c \equiv d \pmod m &\iff a \pm c \equiv b \pm d \pmod m \end{aligned} \]

性质5（同乘性）

\[\begin{aligned} a \equiv b \pmod m &\Rightarrow ac \equiv bc \pmod m\\ a \equiv b \pmod m,c \equiv d \pmod m &\Rightarrow ac \equiv bd \pmod m \end{aligned} \]

性质6（同幂性） \(a \equiv b \pmod m \Rightarrow a^k \equiv b^k \pmod m\) ，其中 \(k \geq 0\)。

性质7（特殊同除性） \(a \equiv b \pmod m \Rightarrow \dfrac{a}{d} \equiv \dfrac{b}{d} \pmod {\dfrac{m}{\gcd(m,d)}}\) ，其中 \(d\) 满足 \(d \mid a,d \mid b\) 。

性质8 若 \(a \equiv b \pmod m\) ，那么 \(m' \mid m \Rightarrow a \equiv b \pmod {m'}\) 。

性质9 \(a \equiv b \pmod {m_i}(i = 1,2,\cdots,k) \iff a \equiv b \pmod{M}\) ，其中 \(M=\text{lcm}(m_1,m_2,\cdots,m_k)\) 。

性质10 \(a \equiv b \pmod m \Rightarrow \gcd(a,m) = \gcd(b,m)\) 。

性质9的证明：

由 \(a \equiv b \pmod {m_i}(i = 1,2,\cdots,k)\) 可得 \(m_i \mid a-b\) ，根据整除基本性质11，可得 \(M \mid a - b,M=\text{lcm}(m_1,m_2,\cdots,m_k)\) ，因此 \(a \equiv b \pmod M\) 。

同余类与剩余系的定义与基本性质

同余类的定义 对于 \(a \in [0,m-1]\) ，集合 \(\{a + km\},k \in \Z\) 的所有数模 \(m\) 同余 \(a\) ，称这个集合为模 \(m\) 的一个同余类 \(\overline a\) 。

完全剩余系的定义 模 \(m\) 的同余类有 \(m\) 个，分别为 \(\overline 0,\overline 1,\cdots ,\overline {m-1}\) ，它们构成了 \(m\) 的完全剩余系。

既约剩余系的定义 模 \(m\) 的同余类有 \(\varphi(m)\) 个的代表元与 \(m\) 互质，它们构成了 \(m\) 的既约剩余系（简化剩余系）。

\(\varphi(m)\) 为欧拉函数，下一节会讲到。

性质1 设 \(S\) 是模 \(m\) 的一个完全剩余系，若 \(\gcd(k,m) = 1\) ，则 \(S' = \{x' \mid x' = kx+b,x\in S \}\) 也是模 \(m\) 的一个完全剩余系。

性质2 设模 \(m_1\) 的完全剩余系为 \(S_1\) ，模 \(m_2\) 的完全剩余系为 \(S_2\) ，且 \(\gcd(m_1,m_2) = 1\) ，则模 \(m = m_1m_2\) 的完全剩余系为 \(S = \{x\mid x = m_2x_1 + m_1x_2,x_1 \in S_1,x_2 \in S_2\}\) 。

性质3 设 \(S\) 是模 \(m\) 的一个既约剩余系，若 \(\gcd(k,m) = 1\) ，则 \(S' = \{x' \mid x' = kx,x\in S \}\) 也是模 \(m\) 的一个既约剩余系。

性质4 设模 \(m_1\) 的既约剩余系为 \(S_1\) ，模 \(m_2\) 的既约剩余系为 \(S_2\) ，且 \(\gcd(m_1,m_2) = 1\) ，则模 \(m = m_1m_2\) 的既约剩余系为 \(S = \{x\mid x = m_2x_1 + m_1x_2,x_1 \in S_1,x_2 \in S_2\}\) 。

• 推论1（性质4的推论） \(\gcd(m_1,m_2) = 1 \Rightarrow \varphi(m_1m_2) = \varphi(m_1)\varphi(m_2)\) ，即欧拉函数是积性函数。

性质1的证明：

假设存在 \(kx_i + b \equiv kx_j + b \pmod m\) ，则 \(kx_i \equiv kx_j \pmod m\) 。因为 \(\gcd(k,m) = 1\) ，所以 \(x_i \equiv x_j \pmod m\) ，\(x_i,x_j\) 属于一个同余类，矛盾。综上，得证。

性质2的证明：

假设存在 \(m_2x_1 + m_1x_2 \equiv m_2x_1'+m_1x_2' \pmod m\) ，那么 \(m_2(x_1-x_1') \equiv m_1(x_2'-x_2) \pmod m\) 。因为 \(m_1 \mid m\) ，所以 \(m_2(x_1-x_1') \equiv m_1(x_2'-x_2) \equiv 0 \pmod {m_1}\) ，又 \(\gcd(m_1,m_2) = 1\) ，所以 \(x_1-x_1' \equiv 0 \pmod {m_1}\) ，矛盾。综上，得证。

性质3的证明：

根据性质1证明，类似可得 \(S'\) 一定是 \(m\) 的一个剩余系，且有 \(\varphi(m)\) 个元素，接下来只需证明任意元素都与 \(m\) 互质。

任意 \(x \in S\) ，有 \(\gcd(x,m) = 1\) ，又 \(\gcd(k,m) = 1\) ，所以 \(\gcd(kx,m) = 1\) ，所以 \(S'\) 是模 \(m\) 的既约剩余系。

性质4的证明：

根据性质2证明，类似可得 \(S\) 一定是模 \(m\) 的一个剩余系，且有 \(\varphi(m_1)\cdot\varphi(m_2)\) 个元素，但我们并不知道 \(\varphi(m_1)\cdot\varphi(m_2) = \varphi(m_1m_2)\) ，因此我们证明 \(S\) 的元素都与 \(m\) 互质只能说明 \(S\) 是模 \(m\) 的既约剩余系的一个子集，我们还需要证明模 \(m\) 的既约剩余系是 \(S\) 的一个子集。

若 \(\gcd(x_1,m_1) = \gcd(x_2,m_2) = 1\) ，又 \(\gcd(m_1,m_2) = 1\) ，因此 \(\gcd(m_2x_1,m_1) = \gcd(m_1x_2,m_2) = 1\) ，所以 \(\gcd(m_2x_1 + m_1x_2,m_1) = \gcd(m_1x_2+m_2x_1,m_2) = 1\) ，于是 \(\gcd(m_1x_2+m_2x_1,m_1m_2) = 1\) ，即 \(S\) 是模 \(m\) 的既约剩余系的子集。

因为 \(\gcd(m_1,m_2) = 1\) ，因此 \(m_2x_1+m_1x_2\) 可以表达所有整数。那么令模 \(m\) 的既约剩余系的元素为 \(m_2x_1+m_1x_2\) ，则 \(\gcd(m_2x_1+m_1x_2,m_1m_2) = 1\) ，因此 \(\gcd(m_2x_1+m_1x_2,m_1) = \gcd(m_2x_1+m_1x_2,m_2) = 1\) ，所以 \(\gcd(m_2x_1,m_1) = \gcd(m_1x_2,m_2) = 1\) ，又 \(\gcd(m_1,m_2) = 1\) ，于是 \(\gcd(x_1,m_1) = \gcd(x_2,m_2) = 1\) ，即模 \(m\) 的既约剩余系是 \(S\) 的子集。

综上 \(S\) 就是模 \(m\) 的既约剩余系。

推论1的证明：

由性质4，可得 \(S\) 的元素个数是 \(\varphi(m_1)\varphi(m_2)\) ，而模 \(m\) 的既约剩余系的元素个数是 \(\varphi(m_1m_2)\) 。因此，当 \(\gcd(m_1,m_2) = 1\) ， \(\varphi(m_1m_2) = \varphi(m_1)\varphi(m_2)\) ，即欧拉函数是积性函数。

欧拉函数

欧拉函数的定义与基本性质

定义 \([1,n]\) 中与 \(n\) 互质的个数记作 \(\varphi(n)\) 。

性质1 \(\varphi(p) = p-1\) ，其中 \(p\) 为素数。

性质2 \(\varphi(p^k) = p^k - p^{k-1}\) ，其中 \(k\in \Z^+\) ， \(p\) 为素数。

性质3 欧拉函数是积性函数，即 \(\gcd(a,b) = 1 \Rightarrow \varphi(ab) = \varphi(a)\cdot \varphi(b)\) 。

性质4（欧拉函数的展开式） \(\displaystyle \varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right)\) 。

性质5 \(p \mid n \text{ 且 } p^2 \not \mid n \Rightarrow \varphi(n) = (p-1)\varphi\left(\dfrac{n}{p}\right)\) ，其中 \(p\) 为素数。

性质6 \(p^2 \mid n \Rightarrow \varphi(n) = p\varphi\left(\dfrac{n}{p}\right)\) ，其中 \(p\) 为素数。

性质4的证明：

由性质3直接可得

\[\begin{aligned} \varphi(n) &= \varphi\left( \prod_{i = 1}^k p_i^{c_i} \right)\\ &= \prod_{i = 1}^k\varphi (p_i^{c_i}) \\ &= \prod_{i = 1}^k (p_i^{c_i}-p_i^{c_i-1})\\ &= n\prod_{p\mid n}\left(1-\frac{1}{p}\right) \end{aligned} \]

其中 \(p\) 是素数。

性质3是由同余类部分证明得到的，比较困难。实际上，我们还能使用容斥原理直接证明，更加简单。

由此还能得出性质5和6。

欧拉函数的求法

试除法

利用试除法的分解质因子，通过性质4累乘即可，适用于只求单个欧拉函数的值。

可以提前 \(O(n)\) 预处理素数，时间复杂度 \(O\left(\dfrac{\sqrt n}{\ln n}\right)\) ，空间复杂度 \(O(n)\) 。

时间复杂度 \(O(\sqrt n)\)

空间复杂度 \(O(1)\)

int euler_one(int n) {
    int ans = n;
    for (int i = 2;i * i <= n;i++) {
        if (!(n % i)) {
            ans = ans / i * (i - 1);
            while (!(n % i)) n /= i;
        }
    }
    if (n > 1)ans = ans / n * (n - 1);
    return ans;
}

线性筛求欧拉函数

对于素数 \(p\) ，直接令 \(\varphi(p) = p-1\) 。

对于合数 \(n\) ，因为只会在 \(i = \dfrac{n}{p}\) 时被最小质因子 \(p\) 筛一次，因此我们可以递推，但需要分类讨论：

1. \(p\) 比 \(i\) 的最小质因子小，满足性质5，因此 \(\varphi(n) = \varphi(p) \cdot \varphi(i) = (p-1)\varphi(i)\) 。
2. \(p\) 是 \(i\) 的最小质因子，满足性质6， \(\varphi(n) = p\varphi(i)\) 。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

const int N = 1e7 + 7;
bool vis[N];
vector<int> prime;
int phi[N];
void get_euler(int n) {
    phi[1] = 1;
    for (int i = 2;i <= n;i++) {
        if (!vis[i]) {
            prime.push_back(i);
            phi[i] = i - 1;
        }
        for (auto j : prime) {
            if (i * j > n) break;
            vis[i * j] = 1;
            if (!(i % j)) {
                phi[i * j] = j * phi[i];
                break;
            }
            phi[i * j] = (j - 1) * phi[i];
        }
    }
}

欧拉函数的其他性质

性质1 当 \(n \geq 3\) 时，\(\varphi(n)\) 为偶数。

性质2 \(f(n) = \displaystyle \sum_{i = 1}^n [\gcd(i,k) = 1] = \left\lfloor\frac{n}{k}\right\rfloor \varphi(n) + f(n \bmod k)\) 。

性质3 \(\displaystyle \sum_{i = 1}^n i[\gcd(i,n) = 1] = \frac{n\varphi(n) + [n = 1]}{2}\) 。

性质4 \(\displaystyle \sum_{d\mid n} \varphi(d) = n\) 。

性质5 \(\varphi(ab) = \dfrac{\varphi(a) \cdot \varphi(b) \cdot \gcd(a,b)}{\varphi(\gcd(a,b))}\) 。

性质6 \(d^2 \mid n \Rightarrow \varphi(n) = d\varphi\left(\dfrac{n}{d}\right)\) 。

• 推论1（性质5和6的推论） 若 \(n = abd^k,k\geq 2\) 且 \(\gcd(a,b)=1\) ，则 \(\varphi(n) = d^{k-2}\varphi(abd^2) = d^{k-2} \dfrac{\varphi(ad) \cdot \varphi(bd) \cdot d}{\varphi(d)}\) 。

性质1的证明：

对于 \(n \geq 3\) ，当 \(m < n\) ，若 \(\gcd(m,n)=1\) ，则 \(\gcd(n-m,n) = 1\) ，同时 \(m \neq n-m\) 。

因此每一个与 \(n\) 互质的数 \(m\) 都对应一个 \(n-m\) 也与 \(n\) 互质，所以 \(\varphi(n)\) 为偶数。

性质2的证明：

\(f(n)\) 等同于 \([1,n]\) 中与 \(k\) 互质的数的个数。

我们把 \([1,n]\) 每 \(k\) 个数分一段，能分完整的 \(\left\lfloor\dfrac{n}{k}\right\rfloor\) 段，以及 \(n \bmod k\) 个多出来的数。

根据 \(\gcd(a,b) = \gcd(a \bmod b,b)\) ，因此 \([1+mk,k+mk]\) 中与 \(k\) 互质的数等于 \([1,k]\) 中与 \(k\) 互质的数，因此完整的 \(\left\lfloor\dfrac{n}{k}\right\rfloor\) 段中，共有 \(\left\lfloor\dfrac{n}{k}\right\rfloor \varphi(k)\) 个与 \(k\) 互质的数。而 \(\left[ 1+\left\lfloor\dfrac{n}{k}\right\rfloor k,n \right]\) 中与 \(k\) 互质的数等于 \([1,n \bmod k]\) 中与 \(k\) 互质的数，即 \(f(n \bmod k)\) 。

综上 \(f(n) = \displaystyle \sum_{i = 1}^n [\gcd(i,k) = 1] = \left\lfloor\frac{n}{k}\right\rfloor \varphi(n) + f(n \bmod k)\) 。

性质3的证明：

左式等同于 \([1,n]\) 中与 \(n\) 互质的数的和。

当 \(n \geq 3\) 时，根据性质 \(1\) ，互质的数一定形如 \(m,n-m\) 成对出现，因此总和的平均值为 \(\dfrac{n}{2}\) ，因此总和为 \(n\dfrac{\varphi(n)}{2}\) 。

当 \(n = 2\) 时，上式也成立。

当 \(n=1\) 时，上式结果为 \(\dfrac{1}{2}\) ，因此增加修正 \(\dfrac{[n=1]}{2}\) 。

综上， \(\displaystyle \sum_{i = 1}^n i[\gcd(i,n) = 1] = \frac{n\varphi(n) + [n = 1]}{2}\) 。

性质4的证明：

令 \(\displaystyle f(x) = \sum_{i=1}^n [\gcd(i,n) = x]\) ，则 \(\displaystyle \sum_{i=1}^n f(i) = n\) ，这是因为每个数的 \(\gcd\) 唯一，遍历一遍 \(\gcd\) 能覆盖 \(n\) 。

又 \(\gcd(i,n) = d \iff \gcd\left( \dfrac{i}{d},\dfrac{n}{d} \right) = 1\) ，所以当 \(x \mid n\) 时， \(\displaystyle f(x) = \sum_{i=1}^{\frac{n}{x}} \left[\gcd\left(i,\frac{n}{x} \right) = 1 \right] = \varphi\left(\frac{n}{x}\right)\) ；当 \(x \not \mid n\) 时， \(f(x) = 0\) 。

综上 \(\displaystyle \sum_{d \mid n} \varphi(d) = \sum_{d \mid n} \varphi\left(\frac{n}{d}\right) = \sum_{d \mid n} f(d) = \displaystyle \sum_{i=1}^n f(i) =n\) 。

性质5的证明：

根据基本性质5可得

\[\begin{aligned} \varphi(ab) &= ab\prod_{p\mid ab}\left(1-\frac{1}{p}\right)\\ &= \frac{\displaystyle a\prod_{p\mid a}\left(1-\frac{1}{p}\right) \cdot b\prod_{p\mid b}\left(1-\frac{1}{p}\right)}{\displaystyle\prod_{p\mid a \cap p\mid b}\left(1-\frac{1}{p}\right)}\\ &= \frac{\varphi(a) \cdot \varphi(b)\cdot\gcd(a,b)}{\displaystyle \gcd(a,b) \prod_{p\mid \gcd(a,b)}\left(1-\frac{1}{p}\right)}\\ &= \dfrac{\varphi(a) \cdot \varphi(b) \cdot \gcd(a,b)}{\varphi(\gcd(a,b))} \end{aligned} \]

性质6的证明：

因为 \(d^2 \mid n\) ，所以 \(n\) 与 \(\dfrac{n}{d}\) 的质因子相同，因此 \(\displaystyle \varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right) = d \cdot \frac{n}{d} \prod_{p\mid \frac{n}{d}}\left(1-\frac{1}{p}\right) = d\varphi\left(\dfrac{n}{d}\right)\) 。

同余重要定理

费马小定理

定理1（费马小定理） 若 \(p\) 为质数且整数 \(a\) 不是 \(p\) 的倍数，则 \(a^{p-1} \equiv 1 \pmod p\) 。

• 推论1（定理1的推论，费马降幂） 若 \(p\) 为质数且整数 \(a\) 不是 \(p\) 的倍数，则 \(a^n \equiv a^{n \mod (p-1)} \pmod p\) 。

定理2（费马大定理） 若整数 \(n \geq 3\) ，则 \(x^n+y^n=z^n\) 无正整数解。

定理1的证明：

由欧拉定理可得， \(\varphi(p) = p-1\) ，且 \(\gcd(a,p)=1\) ，因此 \(a^{p-1} \equiv 1 \pmod p\) 。

欧拉定理见下一节。

定理2的证明：

我有一个绝妙的证明方法，但这里地方太小了我写不下qwq。

欧拉定理

定理1（欧拉定理） 若正整数 \(a,m\) 互质，则 \(a^{\varphi(m)} \equiv 1 \pmod m\) 。

• 推论1（定理1的推论） \(\exist x \in \Z^+ ,a^x \bmod m = 1 \iff \gcd(a,m) = 1\) 。

定理2（拓展欧拉定理，欧拉降幂）

\[a^b \equiv \left\{ \begin{array}{l} a^{b \mod \varphi(m)} &,\gcd(a,m) = 1\\ a^b &,b < \varphi(m) \text{ 且 }\gcd(a,m) \neq 1\\ a^{b \mod \varphi(m) + \varphi(m)} &,b \geq \varphi(m) \text{ 且 }\gcd(a,m) \neq 1\\ \end{array} \right. \pmod m \]

定理1的证明：

设 \(\{x_1,x_2,\cdots,x_{\varphi(m)}\}\) 是一个模 \(m\) 的既约剩余系。

根据同余类与剩余系基本性质3，因为 \(\gcd(a,m) = 1\) ，所以 \(\{ax_1,ax_2,\cdots,ax_{\varphi(m)}\}\) 也是模 \(m\) 的一个既约剩余系。因此， \(x_1x_2\cdots x_{\varphi(m)} \equiv a^{\varphi(m)}x_1x_2\cdots x_{\varphi(m)} \pmod m\) 。

又 \(\gcd(x_1,m) = \cdots = \gcd(x_{\varphi(m)},m) = 1\) ，所以 \(\gcd(x_1x_2 \cdots x_{\varphi(m)},m) = 1\) ，于是 \(a^{\varphi(m)} \equiv 1 \pmod m\) 。

推论1的证明：

从左到右，由条件 \(\exist x \in \N^+,\gcd(a^x,m) = \gcd(a^x \bmod m,m) =\gcd(1,m) = 1\) ，所以 \(\gcd(a^x,m) = \gcd(a,m) = 1\) 。

从右到左，根据欧拉定理显然。

定理2的证明：

见此链接

威尔逊定理

定理1（威尔逊定理） 若 \(p\) 为素数，则满足 \((p-1)! \equiv -1 \pmod p\) 。

定理2（定理1的逆命题） 当 \(p\) 满足 \((p-1)! \equiv -1 \pmod p\) ，则 \(p\) 为素数。

• 推论1（定理1和2的推论） \(p\) 为素数，当且仅当 \((p-1)! \equiv -1 \pmod p\) 。

二元一次不定方程

二元一次不定方程的定义与基本性质

定义 关于整数 \(x,y\) 的方程 \(ax + by = c\) ，其中 \(a,b,c\) 都是整数，称为二元一次不定方程。

裴蜀定理

定理1（裴蜀定理） 关于整数 \(x,y\) 不定方程 \(ax+by = c\) 有解的充要条件是 \(\gcd(a,b) \mid c\) 。

• 推论1 关于整数 \(x,y\) 不定方程 \(ax+by = 1\) 有解的充要条件是 \(\gcd(a,b) = 1\) 。

定理2 关于整数 \(x,y\) 不定方程 \(ax+by = c\) ，满足 \(d = \gcd(a,b),d \mid c\) ，的所有解为

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

其中 \((x_0,y_0)\) 是方程的特解， \(k \in \Z\) 。

定理1的证明：

设 \(d = \gcd(a,b)\) ，则 \(d \mid ax+by\) ，设 \(s\) 为 \(ax+by\) 的最小正值。

根据带余数除法，可得 \(a = qs+r\) ，则 \(r = a - qs = a-q(ax+by) = a(1-qx)+b(-qy)\) ，即 \(r\) 也可以被 \(ax+by\) 表示。

因为 \(r \in [0,s-1]\) ，所以 \(r = 0\) ，即 \(s \mid a\) ，同理 \(s \mid b\) 。因此，\(s \mid d\) ，所以 \(s \leq d\) 。

因为 \(s = ax+by\) ，所以 \(d \mid s\) ， 于是 \(d \leq s\) 。

综上 \(d = s\) ，即 \(\gcd(a,b) = d\) 是 \(ax+by\) 的最小正值。

定理2的证明：

有特解 \((x_0,y_0)\) ，设任意解为 \((x,y)\) ，则 \(ax_0+by_0 = ax+by=c\) ，于是有 \(a(x-x_0) = b(y_0-y)\) 。两边同时除以 \(d\) ，得到 \(\dfrac{a}{d}(x-x_0) = \dfrac{b}{d}(y_0-y)\) ，其中 \(\gcd\left(\dfrac{a}{d},\dfrac{b}{d} \right) = 1\) ，于是 \(\dfrac{a}{d} \mid y_0-y,\dfrac{b}{d} \mid x-x_0\) 。因此有

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

其中 \(k \in \Z\) 。

解二元一次不定方程

从数学角度，二元一次不定方程系数是整数范围的，但使用算法时我们需让 \(a,b\geq 0\) ，详见整除章节 \(\gcd\) 的求法前言。若出现如 \(a<0\) 等系数为负数情况，需转换为 \(|a|(-x) +by = \gcd(a,b)\) 求解。以下的证明建立在正系数之上。

扩展欧几里得算法

对于二元一次不定方程的求解，关键在于求出一组特解。扩展欧几里得算法（extended gcd,exgcd）在辗转相除法的基础上，递归求解关于 \(x,y\) 的方程 \(ax+by = \gcd(a,b)\) 的一组特解。

证明：

考虑方程 \(ax+by = \gcd(a,b) = \gcd\left(b,a-b\left\lfloor \dfrac{a}{b} \right\rfloor\right) = bx' + \left(a-b\left\lfloor \dfrac{a}{b} \right\rfloor\right)y'\) 。

我们可以得到 \(ax+by = ay' + b\left(x'-\left\lfloor \dfrac{a}{b} \right\rfloor y' \right)\) ，于是得到

\[\left\{ \begin{aligned} x &= y'\\ y &= x'-\left\lfloor \dfrac{a}{b} \right\rfloor y'\\ \end{aligned} \right. \]

递归至 \(b = 0\) ，此时 \(ax + 0y = \gcd(a,0) = a\) ，易得 \(x = 1,y = 0\) 是一组解，就可以回溯求解。

通过exgcd求出一组特解以后，即可通过裴蜀定理中的定理2得到所有解。

可以证明exgcd的解 \((x,y)\) 满足 \(|x| \leq b,|y| \leq a\) ，所以在 int 范围内可以都用 int 变量，详见OI-wiki。

以下只提供exgcd的算法。

时间复杂度 \(O(\log(\min\{a,b \}))\)

空间复杂度 \(O(1)\)

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

二元一次不定方程的非负整数解

我们仅讨论 \(a,b,c\geq 1\) 且 \(\gcd(a,b) = 1\) 的情况下，方程 \(ax+by = c\) 的非负整数解，即 \(x,y\geq0\) 的解。

性质1 若 \(c > ab-a-b\) ，则 \(ax+by = c\) 存在非负整数解。

性质2 若 \(c = ab-a-b\) ，则 \(ax+by = c\) 不存在非负整数解。

性质3 若 \(c < ab-a-b\) ，则 \(ax+by = c\) 恰好有 \(\max\left\{0,\dfrac{(a-1)(b-1)}{2} - 2\right\}\) 个 \(c\) 有非负整数解，且解唯一。

性质1的证明：

对于 \(x \in [0,b-1]\) ，$by = c - ax > ab-a-b-ax \geq ab-a-b-a(b-1) = -b $ ，所以 \(y\geq 0\) 。

所以方程有非负解。

性质2的证明：

\(ax+by = ab-a-b\) ，即 \(a(x+1) + b(y+1) = ab\) 。因为 \(\gcd(a,b) = 1\) ，所以 \(a \mid y+1,b \mid x+1\) 。

设 \(ka = y+1,mb = x+1\) ，其中 \(k,m\in \Z^+\) 。代入原式得， \((m+k)ab = ab\) ，所以 \(m+k = 1\) ，所以必有一个小于等于 \(0\) ，即 \(x,y\) 中必有一个小于 \(0\) ，因此没有非负解。

性质3的证明：

分三步证明。

1. 若 \(ax+by = c\) 有非负解，则解 \((x,y) \in [0,b-2]\times [0,a-2]\) 且 \((x,y) \neq (0,0),(b-2,a-2)\) 。

   因为 \(y \geq 0\) ，所以 \(ax = c - by \leq c < ab-a-b\) ，所以 \(x < b - 1 - \dfrac{b}{a}\) ，即 \(x \leq b-2\) 。

   同理 \(y \leq a-2\) 。

   \((x,y) \neq (0,0),(b-2,a-2)\) 可以验证得到。

2. 若 \(ax+by=c\) 有非负解，则最多只有一个非负解。

   若 \((x_0,y_0)\) 是一个非负解，则 \(x_0 \in [0,b-2],y_0 \in[0,a-2]\) 。因为 \(\gcd(a,b) = 1\) ，所以通解为

   \[\left\{ \begin{aligned} x &= x_0 + kb\\ y &= y_0 - ka \end{aligned} \right. \]

   其他解一定不在 \([0,b-2]\times[0,a-2]\) 中，一定不是解，因此只有一个非负解。

3. 当 \((x,y) \in [0,b-2]\times [0,a-2]\) 且 \((x,y) \neq (0,0),(b-2,a-2)\) ， \((x,y)\) 是 \(ax+by = c\) 的一个非负解，当且仅当 \((b-2-x,a-2-y)\) 不是任何 \(c < ab-a-b\) 的非负解。

   必要性：

   \(ax+by = c<ab-a-b\) ，所以

   \[\begin{aligned} a(b-2-x)+b(a-2-y) &= ab-2a-ax+ab-2b-by\\ &=2(ab-a-b)-(ax+by)\\ &>ab-a-b \end{aligned} \]

   因此 \((b-2-x,a-2-y)\) 不是任何 \(c<ab-a-b\) 的非负解。

   充分性：

   因为 \((b-2-x,a-2-y)\) 不是任何 \(c<ab-a-b\) 的非负解，且 \(a(b-2-x)+b(a-2-y) > 0\) 以及 \(c = ab-a-b\) 没有非负解，因此 \(a(b-2-x)+b(a-2-y) > ab-a-b\) ，所以

   \[\begin{aligned} a(b-2-x)+b(a-2-y) &= ab-2a-ax+ab-2b-by\\ &=2(ab-a-b)-(ax+by)\\ &> ab-a-b \end{aligned} \]

   于是 \(ax+by < ab-a-b\) ，又 \(ax+by > 0\) ，所以 \((x,y)\) 一定是 \(c < ab-a-b\) 的一个非负解。

综上，当 \(c<ab-a-b\) 时，

由1得知，解一定出现在 \((x,y) \in [0,b-2]\times [0,a-2]\) 且 \((x,y) \neq (0,0),(b-2,a-2)\) 。

由3得知，有解和无解一定成对出现，所以共 \(\max\left\{0,\dfrac{(a-1)(b-1)}{2} - 2\right\}\) 个解。

由2得知，解和 \(c\) 是一一对应的，所以共 \(\max\left\{0,\dfrac{(a-1)(b-1)}{2} - 2\right\}\) 个 \(c\) 有解。

乘法逆元

乘法逆元的定义与基本性质

定义 当且仅当 \(\gcd(a,m) = 1\) 时，存在整数 \(x\) 满足 \(ax \equiv 1 \pmod m\) ，我们称 \(x\) 为 \(a\) 在模 \(m\) 意义下的逆元，记作 \(a^{-1}\) 。

乘法逆元的求法

费马小定理法

若 \(m\) 为质数且整数 \(a\) 不是 \(m\) 的倍数，则 \(a^{m-1} \equiv a \cdot a^{m-2} \equiv 1 \pmod m\) ，其中 \(a^{m-2}\) 即为所求逆元。

时间复杂度 \(O(\log m)\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;
int qpow(int a, ll k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = 1LL * ans * a % P;
        k >>= 1;
        a = 1LL * a * a % P;
    }
    return ans;
}
int inv(int x) { return qpow(x, P - 2); }

扩展欧几里得算法

若 \(\gcd(a,m) = 1\) ，那么 \(ax \equiv 1 \pmod m \iff ax + my = 1\) 一定存在解，即一定有 \(a\) 在模 \(m\) 意义下的逆元 \(a^{-1} = x\) 。因此，我们可以解 \(ax+my = 1\) ，利用exgcd可以直接求解。

时间复杂度 \(O(\log(\min\{a,m \}))\)

空间复杂度 \(O(1)\)

const int P = 1e9 + 7;
int exgcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1, y = 0; return a; }
    int d = exgcd(b, a % b, x, y);
    x -= (a / b) * y, swap(x, y);
    return d;
}
int inv(int a) {
    int x, y;
    exgcd(a, P, x, y);
    return (x % P + P) % P;
}

线性递推求乘法逆元

若需要频繁使用 \([1,n]\) 内模 \(m\) 的逆元，其中 \(n<m\) 且 \(m\) 为质数，可以考虑预处理 \([1,n]\) 的所有逆元。枚举每个数字朴素求逆元是线性对数复杂度的，但事实上存在一种递推的求法，可以在线性复杂度内从 \(1\) 递推出 \([1,n]\) 的所有逆元。

证明：

当 \(i = 1\) 时，我们有 \(1 \cdot 1 \equiv 1 \pmod m\) ，因此 \(1^{-1} = 1\) 。

当 \(i > 1\) 时，考虑 \(m = \left\lfloor \dfrac{m}{i} \right\rfloor \cdot i + m \bmod i = pi+r\) ，于是有

\[\begin{aligned} m &\equiv 0 \pmod m\\ pi+r &\equiv 0 \pmod m\\ pr^{-1} + i^{-1} &\equiv 0 \pmod m\\ i^{-1} &\equiv -pr^{-1} \pmod m\\ i^{-1} &\equiv -\left\lfloor \dfrac{m}{i} \right\rfloor \cdot (m \bmod i)^{-1} \pmod m \end{aligned} \]

因此，我们可以从 \(1 \leq m \bmod i < i\) 的逆元推出 \(i\) 的逆元。

在这里我们使用 \(\left( m-\left\lfloor \dfrac{m}{i} \right\rfloor \right) \cdot (m \bmod i)^{-1}\) 防止出现负数。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

const int P = 1e9 + 7;
const int N = 1e7 + 7;
int inv[N];
void init(int n) {
    inv[1] = 1;
    for (int i = 2;i <= n;i++) inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
}

线性递推求阶乘逆元

通常在组合数学中需要频繁 \(i!,i\in[1,n]\) 模 \(m\) 的逆元，其中 \(n<m\) 且 \(m\) 为质数，我们同样也可以线性递推。我们可以线性求出 \([1,n]\) 的逆元后再求阶乘的逆元，也可以从 \((n!)^{-1}\) 倒推。我们采用倒推的方法。

证明：

已知 \((n!)^{-1}\) ，可以递推求出 \(n!\) 后，用费马小定理或exgcd求解 \((n!)^{-1}\) 。

当 \(1 \leq i < n\) 时，有 $(i!)^{-1} \equiv ((i+1)!)^{-1} \cdot (i+1) \pmod m $ 。

因此，我们可以从 \((i+1)!\) 的逆元推出 \(i!\) 的逆元。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

const int P = 1e9 + 7;
const int N = 1e7 + 7;
int qpow(int a, ll k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans = 1LL * ans * a % P;
        k >>= 1;
        a = 1LL * a * a % P;
    }
    return ans;
}
int fact[N], invfact[N];
void init(int n) {
    fact[0] = 1;
    for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
    invfact[n] = qpow(fact[n], P - 2);
    for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
}

一元一次同余方程

一元一次同余方程的定义与基本性质

定义 关于整数 \(x\) 的方程 \(ax \equiv b \pmod m\) ，其中 \(a,b\) 为整数， \(m\) 为正整数，称为一元一次同余方程。

约定 关于整数 \(x\) 的方程 \(ax \equiv b \pmod m\) ，我们认为在模 \(m\) 下同余的解 \(x\) 是同一个解。

解数的定义 方程不同的解的个数为方程的解数。

性质1 关于整数 \(x\) 的一元一次同余方程 \(ax \equiv b \pmod m\) ，等价于关于整数 \(x,y\) 的二元一次不定方程 \(ax+my = b\) ，其中 \(x\) 意义相同。因此，二元一次不定方程的性质与定理可以直接用于一元一次同余方程。

性质2 关于整数 \(x\) 的一元一次同余方程 \(ax \equiv b \pmod m\) ，其解数为 \(\gcd(a,m)\) 。

性质2的证明：

通过性质1转换成二元一次不定方程，可求方程的所有解，容易发现解数为 \(\gcd(a,m)\) 。

解一元一次同余方程

扩展欧几里得算法

关于整数 \(x\) 的同余方程 \(ax \equiv b \pmod m\) ，根据性质1，可以转化为关于整数 \(x,y\) 的不定方程 \(ax+my = b\) ，于是同前面所说的不定方程的解法一致。

时间复杂度 \(O(\log(\min\{a,m \}))\)

空间复杂度 \(O(1)\)

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

一元一次同余方程组

一元一次同余方程组的定义与基本性质

定义 关于整数 \(x\) 的方程组

\[\left\{ \begin{aligned} a_1x &\equiv b_1 \pmod{m_1}\\ a_2x &\equiv b_2 \pmod{m_2}\\ \vdots \\ a_kx &\equiv b_k \pmod{m_k}\\ \end{aligned} \right. \]

其中 \(a_i,b_i(1 \leq i \leq k)\) 为整数，\(m_i(1 \leq i \leq k)\) 为正整数，称为一元一次同余方程组。

约定 关于整数 \(x\) 的方程组 \(a_ix \equiv b_i \pmod {m_i}(1\leq i \leq k)\) ，我们认为在模 \(M = \text{lcm}(m_1,m_2,\cdots,m_k)\) 下同余的解 \(x\) 是同一个解。

解数的定义 方程组不同的解的个数为方程组的解数。

性质1 对于任意关于 \(x\) 的一元一次同余方程组

\[\left\{ \begin{aligned} a_1x &\equiv b_1 \pmod{m_1}\\ a_2x &\equiv b_2 \pmod{m_2}\\ \vdots \\ a_kx &\equiv b_k \pmod{m_k}\\ \end{aligned} \right. \]

等价于如下系数为 \(1\) 的方程组

\[\left\{ \begin{aligned} x &\equiv a_{1,1} \pmod{m_1}\\ \vdots \\ x &\equiv a_{1,c_1} \pmod{m_1}\\ x &\equiv a_{2,1} \pmod{m_2}\\ \vdots \\ x &\equiv a_{2,c_2} \pmod{m_2}\\ \vdots \\ x &\equiv a_{k,1} \pmod{m_k}\\ \vdots \\ x &\equiv a_{k,c_k} \pmod{m_k}\\ \end{aligned} \right. \]

其中 \(c_i(1 \leq i \leq k)\) 为第 \(i\) 个方程 \(a_ix \equiv b_i \pmod{m_i}\) 的解数， \(a_{i,j}(1 \leq i \leq k,1\leq j \leq c_i)\) 为第 \(i\) 个方程 \(a_ix \equiv b_i \pmod{m_i}\) 的第 \(j\) 个解。

性质2 对于有如下形式的一元一次同余方程组

\[\left\{ \begin{aligned} x &\equiv a_1 \pmod{m_1}\\ x &\equiv a_2 \pmod{m_2}\\ \vdots \\ x &\equiv a_k \pmod{m_k}\\ \end{aligned} \right. \]

其解 \(x\) 与 \(M = \text{lcm}(m_1,m_2,\cdots,m_k)\) 满足 \(\gcd(a_i,m_i) = 1(1\leq i \leq k) \iff \gcd(x,M) = 1\) 。

性质1的证明：

对方程组中每个一元一次同余方程求解，可得对应方程的解集。显然，解集方程与原方程是同解的，可以等价替换原方程。

性质2的证明：

解 \(x\) 满足 \(x \equiv a_i \pmod {m_i}(1\leq i \leq k)\) ， 根据同余基本性质10，有 \(\gcd(x,m_i) = \gcd(a_i,m_i)\) 。

随后，结合 \(\gcd\) 基本性质6，有 \(\gcd(a_i,m_i) = \gcd(x,m_i) = 1 \iff \gcd(x,M) = 1\) ，因此得证。

中国剩余定理（孙子定理）

定理1（中国剩余定理） 对于有如下形式且满足 \(m_1,m_2,\cdots ,m_k\) 两两互质的一元一次同余方程组

\[\left\{ \begin{aligned} x &\equiv a_1 \pmod{m_1}\\ x &\equiv a_2 \pmod{m_2}\\ \vdots \\ x &\equiv a_k \pmod{m_k}\\ \end{aligned} \right. \]

必有解，且解数为 \(1\) 。

定理1的证明：

设 \(\displaystyle M = \text{lcm}(m_1,\cdots ,m_k) = \prod_{i=1}^k m_i\) ， \(M_i = \dfrac{M}{m_i}\) ， \(M_i\) 在模 \(m_i\) 下的必有逆元为 \(M_i^{-1}\) 。

所以，我们可以构造出 \(x = \displaystyle \sum_{i=1}^k a_iM_iM_i^{-1}\) ，容易证明 \(x\) 是符合方程组的一个解。

同时，对于任意两个解 \(x_1,x_2\) ，我们有 \(x_1 \equiv x_2 \pmod{m_i} (i = 1,\cdots,k)\) ，根据同余基本性质9，可得 \(x_1 \equiv x_2 \pmod M\) 。因此，解在模 \(\displaystyle M = \text{lcm}(m_1,\cdots ,m_k) = \prod_{i=1}^k m_i\) 下是唯一的，即解数为 \(1\) 。

换句话说，如此方程在 \([0,M)\) 中的必有解且唯一，即其最小正整数解 \(x_{min}\) 。

解一元一次同余方程组

中国剩余定理

对于一般的一元一次同余方程组，都可以化为有如下形式（即系数为 \(1\) ）的同余方程组

\[\left\{ \begin{aligned} x &\equiv a_1 \pmod{m_1}\\ x &\equiv a_2 \pmod{m_2}\\ \vdots \\ x &\equiv a_k \pmod{m_k}\\ \end{aligned} \right. \]

若方程组还满足 \(m_1,m_2,\cdots ,m_k\) 两两互质，则可以用中国剩余定理（Chinese Remainder Theorem, CRT）证明中的构造法求解。

时间复杂度 \(O(k \log(\max\{m_i\}))\)

空间复杂度 \(O(k)\)

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x = 1, y = 0; return a; }
    ll d = exgcd(b, a % b, x, y);
    x -= (a / b) * y, swap(x, y);
    return d;
}
ll inv(ll a, ll P) {
    ll x, y;
    exgcd(a, P, x, y);
    return (x % P + P) % P;
}
ll CRT(int k, const vector<int> &a, const vector<int> &m) {
    ll M = 1, ans = 0;
    for (int i = 1;i <= k;i++) M *= m[i];
    for (int i = 1;i <= k;i++) {
        ll Mi = M / m[i], invMi = inv(Mi, m[i]);
        (ans += (__int128_t)a[i] * Mi * invMi % M) %= M;
    }
    return ans;
}

扩展中国剩余定理

若一般的一元一次同余方程组化为的同余方程组

\[\left\{ \begin{aligned} x &\equiv a_1 \pmod{m_1}\\ x &\equiv a_2 \pmod{m_2}\\ \vdots \\ x &\equiv a_k \pmod{m_k}\\ \end{aligned} \right. \]

其模数 \(m_1,m_2,\cdots ,m_k\) 不满足两两互质，那么CRT是无法解决的。我们就需要使用扩展中国剩余定理（extended CRT,exCRT），虽说名字叫exCRT，但和CRT没有任何关系，单纯是CRT失效的时候用的一种新算法。

exCRT面对这种情况，采用的是朴素合并方程的方法。在对方程进行 \(k-1\) 次合并后，得到最后一个方程，即方程组的解。

证明：

先考虑合并两个方程

\[\left\{ \begin{aligned} x &\equiv a_1 \pmod{m_1}\\ x &\equiv a_2 \pmod{m_2}\\ \end{aligned} \right. \]

根据一元一次同余方程基本性质1，我们可以将方程组改写为二元一次不定方程组

\[\left\{ \begin{aligned} x &= m_1p_1 + a_1\\ x &= m_2p_2 + a_2\\ \end{aligned} \right. \]

我们将两个方程相减可得 \(m_1p_1 + m_2(-p_2) = a_2 - a_1\) ，根据裴蜀定理，当且仅当 \(\gcd(m_1,m_2) \mid a_2-a_1\) 时，该方程有解。

在有解的情况，通过exgcd可求出 \(m_1p_1 + m_2(-p_2) = \gcd(m_1,m_2)\) 的一组特解 \(p_1',-p_2'\) ，根据裴蜀定理的定理 \(2\) 得原方程的所有解为

\[\left\{ \begin{aligned} P_1 &= p_1' \cdot \dfrac{a_2-a_1}{\gcd(m_1,m_2)} + \dfrac{km_2}{\gcd(m_1,m_2)} \\ -P_2 &= (-p_2') \cdot \dfrac{a_2-a_1}{\gcd(m_1,m_2)} - \dfrac{km_1}{\gcd(m_1,m_2)} \\ \end{aligned} \right. \]

其中 \(k \in \Z\) 。

将通解 \(P_1\) 代入 \(x = m_1p_1+a_1\) ，则有

\[\begin{aligned} x &= a_1 + m_1p_1' \cdot \dfrac{a_2-a_1}{\gcd(m_1,m_2)} + \dfrac{km_1m_2}{\gcd(m_1,m_2)}\\ &= a_1 + m_1p_1' \cdot \dfrac{a_2-a_1}{\gcd(m_1,m_2)} + k\cdot \text{lcm}(m_1,m_2) \end{aligned} \]

其等价于同余方程 \(x \equiv a_1+m_1p_1' \cdot \dfrac{a_2-a_1}{\gcd(m_1,m_2)} \pmod{\text{lcm}(m_1,m_2)}\) ，于是我们就合并了两个方程。

对于原方程组

\[\left\{ \begin{aligned} x &\equiv a_1 \pmod{m_1}\\ x &\equiv a_2 \pmod{m_2}\\ \vdots \\ x &\equiv a_k \pmod{m_k}\\ \end{aligned} \right. \]

只需要进行 \(k-1\) 次合并即可。

在实现的过程中，原方程的特解 \(p_1' \cdot \dfrac{a_2-a_1}{\gcd(m_1,m_2)}\) 可以模 \(\dfrac{m_2}{\gcd(m_1,m_2)}\) （注意 \(a_2-a_1\) 可能是负数，但不影响exgcd求解，只影响 % 运算的结果），可以避免一部分数字溢出。

时间复杂度 \(O(k \log(\max\{m_i\}))\)

空间复杂度 \(O(k)\)

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x = 1, y = 0; return a; }
    ll d = exgcd(b, a % b, x, y);
    x -= (a / b) * y, swap(x, y);
    return d;
}
ll exCRT(int k, const vector<ll> &a, const vector<ll> &m) {
    ll ans = a[1], M = m[1];
    for (int i = 2;i <= k;i++) {
        ll x, y;
        ll d = exgcd(M, m[i], x, y);
        ll c = a[i] - ans;
        if (c % d) return -1;
        ll md = m[i] / d;
        x = ((__int128_t)c / d * x % md + md) % md;
        ans += M * x;
        M *= md;
        ans %= M;
    }
    return ans;
}

特殊求和问题

问题描述

给定正整数 \(n\) 以及非负整数 \(a,b,c\) ，分别求

\[\begin{aligned} \sum_{i = 0}^n \left\lfloor \dfrac{ai+b}{c} \right\rfloor , \sum_{i = 0}^n \left\lfloor \dfrac{ai+b}{c} \right\rfloor^2 , \sum_{i = 0}^n i\left\lfloor \dfrac{ai+b}{c} \right\rfloor \end{aligned} \]

求解方式

类欧几里得算法

暂时不学。

标签：gcd,数论,笔记,pmod,int,varphi,left,同余,equiv
From： https://www.cnblogs.com/BlankYang/p/17051072.html