数论笔记-整除

整除

整除的定义与基本性质

定义 设 \(a,b \in \Z\) ，若 \(b\) 除以 \(a\) 余数为 \(0\) ，则称 \(a\) 整除 \(b\) ，记为 \(a \mid b\) 。

设 \(a,b,c \in \Z\) 。

性质1 \(a \mid b \text{ 且 } b \mid c \Rightarrow a \mid c\) 。

性质2 \(a \mid b \Rightarrow a \mid kb\) ，其中 \(k \in \Z\) 。

性质3 \(a\mid b \iff ka \mid kb\) ，其中 \(k \in \Z^*\)。

性质4 \(a \mid b \text{ 且 } a \mid c \Rightarrow a \mid kb + mc\) ，其中 \(k,m\in \Z\) 。

性质5 \(a \mid b \text{ 且 } b \mid a \Rightarrow a = \pm b\) 。

性质6 \(a\mid b \Rightarrow |a| \leq |b|\) ，其中 \(b \neq 0\) 。

性质7 当 \(c=ka + b\) ，则 \(a\mid b \iff a\mid c\) ，其中 \(a \neq 0 , k \in \Z\) 。

性质8 \(a = kb \pm c \Rightarrow a,b \text{ 的公因数与 } b,c \text{ 的公因数相同}\) 。

性质9 \(a \mid bc \text{ 且 } \gcd (a,c) = 1 \Rightarrow a \mid b\) 。

性质8证明：

设 \(a,b\) 任意公因数为 \(d\) ，那么 \(a = kb \pm c \Rightarrow c = \pm(a-kb)\) ，因此 \(c\) 也有因数 \(d\) ，所以 \(b,c\) 有公因数 \(d\) 。

设 \(b,c\) 任意公因数为 \(d\) , 那么显然 \(a\) 也有因数 \(d\) ，所以 \(a,b\) 具有公因数 \(d\) 。

综上 \(a,b\) 的公因数与 \(b,c\) 的公因数相同。

素数

素数的定义与基本性质

定义 素数（质数）是只有 \(1\) 和它本身两个因数的数，否则为合数。

约定 \(1\) 既不是素数，也不是合数。

偶素数 \(2\) 是唯一的偶素数。

素数定理

设 \(\pi(n)\) 为 \([1,n]\) 中素数的个数。

素数分布存在渐进， \(\pi(n) \sim \dfrac{n}{\ln n},n \rightarrow \infty\) 。

由素数定理，可以得到如下定理：

定理1 对于 \(n \in \N^+\) ，有 \(\pi(n) \approx \dfrac{n}{\ln n}\) 。

定理2（伯特兰-切比雪夫定理） 对于任意整数 \(n\geq 4\) ，存在质数 \(p\) 满足 \(n < p < 2n-2\) 。

推论1（定理2的推论） 对于任意整数 \(n\geq 2\) ，存在质数 \(p\) 满足 \(n < p < 2n\) 。

素数判定

试除法

一个数 \(n\) 若是合数，则一定在 \([1,\sqrt n]\) 中存在一个质数整除 \(n\) 。

证明：

设 \(d\) 是 \(n\) 的一个质因子，则 \(\dfrac{n}{d}\) 也能整除 \(n\) 。假设 \(d \leq \dfrac{n}{d}\) ，则 \(d \leq \sqrt{n}\) 。

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

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

bool isPrime(int n) {
    if (n == 2) return 1;
    if (n == 1) return 0;
    for (int i = 2;i * i <= n;i++) if (!(n % i)) return 0;
    return 1;
}

\(kn+i\) 法

试除法的升级版，常数更小。

一个数 \(n\) 若是合数，则一定存在 \([1,\sqrt n]\) 的质因子。因此，在试除法的基础上，枚举因子时只考虑可能成为质因子的因子。

例如 \(k = 30\) 时，只有 \(i = 1,7,11,13,17,19,23,29\) 时的数才有可能成为质因子，其他情况都与 \(30\) 有非 \(1\) 的公因子一定不是素数。如此，算法计算量变为原来的 \(\dfrac{4}{15}\) 。

\(k = 30\) 时，时间复杂度 \(O(\frac{4}{15} \sqrt n)\)

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

bool isPrime(int n) {
    if (n == 2 || n == 3 || n == 5) return 1;
    if (n == 1 || !(n % 2) || !(n % 3) || !(n % 5)) return 0;
    int a[8] = { 4,2,4,2,4,6,2,6 }, p = 0;
    for (int i = 7;i * i <= n;i += a[p++], p %= 8) if (!(n % i)) return 0;
    return 1;
}

预处理法

欧拉筛 \(O(n)\) 预处理所有素数后，试除法可以直接枚举质因子。

根据素数定理，素数占比约为 \(\dfrac{1}{\ln n}\) ，因此复杂度变为原来的 \(\dfrac{1}{\ln n}\)。

时间复杂度 \(O(\frac{\sqrt n}{\ln n})\)

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

Miller-Rabin素性测试

Miller-Rabin素性测试通常用于判定大数（远超 \(2^{64}\) 范围）是否为素数，其是费马素性测试的改进版。

众所周知，费马小定理：

当 \(a\) 不是 \(p\) 的倍数，若 \(p\) 为素数，则 \(a^{p-1} \equiv 1 \pmod p\) 。

但其逆命题：

当 \(a\) 不是 \(p\) 的倍数，若 \(a^{p-1} \equiv 1 \pmod p\) ，则 \(p\) 为素数。

并不总是成立。例如，\(2^{341-1} \equiv 1 \pmod{341},3^{1105-1} \equiv 1 \pmod{1105}\) ，这些数称为费马伪素数。

但事实上，费马伪素数的概率并不是很大。我们可以对一个数 \(p\) 取 \(k\) 个 \(a\) 测试，若存在 \(a^{p-1} \not\equiv 1 \pmod p\) ，则 \(p\) 一定是合数；否则，\(p\) 很大概率是素数。这个过程称为费马素性测试，时间复杂度为 \(O(k \log n)\) 。可惜的是，到 long long 范围，费马素性测试的准确性就已经开始不高了。因此，在此基础上有了改进的算法Miller-Rabin素性测试 。

Miller-Rabin素性测试在费马素性测试的基础上增加了二次探测定理的使用。二次探测定理：

若 \(p\) 为奇素数，则 \(x^2 \equiv 1 \pmod p\) 的解为 $x \equiv \pm 1 \pmod{p} $ 。特别地，在 \([0,p-1]\) 的解为 \(x = 1\) 或 \(x = p-1\) 。

因为只能探测奇素数，所以偶数要开始前判掉。

我们先将 \(p-1\) 拆分为 \(2^rm\) （\(m\) 为奇数，\(r \geq 1\) ），随后考虑对 \(x = a^m,a^{2m},\cdots,a^{2^{r-1}m}\) 进行二次探测。根据费马素性测试，这个 \(x\) 序列探测到最后的结果应是 \(1\) 。我们对出现 \(1\) 的情况分类讨论：

1. 如果一开始 \(a^{m} \equiv \pm 1 \pmod p\) 成立，后续探测全是 \(x^2 \equiv 1 \pmod p\) 就不需要判断了。
2. 若不成立，则一定要在 \(r-1\) 次探测内先得到 \(x^2 \equiv - 1 \pmod p\) ，否则最后一定出现结果不为 \(1\) 或者出现 \(x^2 \equiv 1 \pmod p\) 但 \(x \not \equiv \pm 1 \pmod p\) 的情况，则 \(p\) 为合数。

判定大数 \(n\) 是否为素数的具体步骤：

1. 特判 \(n=1,2\) 以及其他所有偶数。
2. 将 \(n-1\) 拆分成 \(2^rm\) ，若 \(a^{m} \equiv \pm 1 \pmod{n}\) ，则后续全是 \(1\) 不需要判断，否则下一步。
3. 枚举 \(k\) 个（通常为 \(8\) 到 \(10\) 个） \(a \in [1,n-1]\) 保证不是 \(n\) 的倍数，对 \(x = a^m,a^{2m},\cdots,a^{2^{r-2}m}\) 进行共 \(r-1\) 次二次探测，是否经过 \(-1\) 。
4. 若 \(k\) 次测试都通过，则 \(n\) 大概率为素数；某次没通过就一定是合数。

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

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

namespace Miller_Rabin {
    template<class T>
    T randint(T l, T r) {
        static mt19937 eng(time(0));
        uniform_int_distribution<T> dis(l, r);
        return dis(eng);
    }
    ll qpow(ll a, ll k, ll P) {
        ll ans = 1;
        while (k) {
            if (k & 1) ans = (__int128_t)ans * a % P;
            k >>= 1;
            a = (__int128_t)a * a % P;
        }
        return ans;
    }
    bool isPrime(ll n, int k = 10) {//8-10次
        if (n == 2) return 1;
        if (n == 1 || !(n & 1)) return 0;
        int r = __builtin_ctzll(n - 1);
        ll m = n - 1 >> r;
        while (k--) {
            ll x = qpow(randint(1LL, n - 1), m, n);
            if (x == 1 || x == n - 1) continue;//直接满足,否则r-1次内必须有n-1
            for (int i = 1;i <= r - 1 && x != 1 && x != n - 1;i++) x = (__int128_t)x * x % n;//二次探测
            if (x != n - 1) return 0;//未经过n-1
        }
        return 1;
    }
}

素数筛法

埃氏筛

素数的倍数一定是合数，合数的倍数一定被某个质因子的倍数筛掉了，因此我们只需要筛掉素数的倍数。

在 \(2\times 10^7\) 内，还是能跑到 \(1\) 秒以内的，再大就不行了。

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

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

const int N = 1e7 + 7;
bool vis[N];
vector<int> prime;
void get_prime(int n) {
    for (int i = 2;i <= n;i++) {
        if (vis[i]) continue;
        prime.push_back(i);
        for (int j = 2;j * i <= n;j++) vis[i * j] = 1;
    }
}

欧拉筛（线性筛）

埃氏筛的时间复杂度已经很优秀了，但依旧会造成一个合数被筛多次的情况，我们希望每个合数都只被筛一次。因此，我们有欧拉筛，每个合数只会被其最小质因子筛掉。

证明：

假设对于 \(i \in [2,n]\) 的每个数，设其最小质因子为 \(p\) ，我们只筛到其 \(p\) 倍。

1. 先证明任意合数 \(n\) 都能被最小质因子筛一次。

   任意合数 \(n\) ，设其最小质因子为 \(p'\) ，则 \(i = \dfrac{n}{p’}\) ，那么有 \(p' \leq p\) ，因此 \(n\) 一定能在 \(i\) 的 \(p\) 倍时或者之前被其最小质因子 \(p'\) 筛掉。

2. 再证明任意合数 \(n\) 不会被非最小质因子筛掉。

   任意合数 \(n\) ，设其最小质因子为 \(p'\) ，其他任意质因子为 \(p''\)， 有 \(p'' > p'\) ，则 \(i = \dfrac{n}{p''}\) 的最小质因子 \(p = p' < p''\) ，因此 \(n\) 根本不会被某个数的 \(p''\) 倍筛掉。

因此，我们对每个数只筛到其最小质因子倍，就能保证筛掉的每个数只会被其最小质因子筛一次。

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

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

const int N = 1e7 + 7;
bool vis[N];
vector<int> prime;
void get_prime(int n) {
    for (int i = 2;i <= n;i++) {
        if (!vis[i]) prime.push_back(i);
        for (int j = 0;j < prime.size() && i * prime[j] <= n;j++) {
            vis[i * prime[j]] = 1;
            if (!(i % prime[j])) break;
        }
    }
}

反素数

反素数的定义与基本性质

定义 对于正整数 \(n\) ，满足任何小于 \(n\) 的数的因子个数都小于 \(n\) 的因子个数。

性质1 \([1,n]\) 中的反素数，一定是相同因子个数的数中最小的。

显然对于任意 \(n \in [1,2^{31}]\) ，其质因子不会超过 \(10\) 个，且质因子的指数之和不会超过 \(31\) 。

性质2 当 \(x \in [1,n],n\leq 2^{31}\) ，则 \(x\) 是反素数的必要条件是 \(x = 2^{c_1} \times 3^{c_2} \times 5^{c_3} \times 7^{c_4} \times 11^{c_5} \times 13^{c_6} \times 17^{c_7} \times 19^{c_8} \times 23^{c_9} \times 29^{c_{10}}\) ，其中 \(c_1 \geq c_2 \geq \cdots \geq c_{10} \geq 0\) 。

枚举反素数

根据性质2，我们可以通过dfs枚举每个质因子的指数，进而求出可能为反素数的数。再求其因子个数，根据性质1，取相同因子个数中最小的那个数即可筛选出所有反素数。

正整数结构

唯一分解定理

任何一个大于 \(1\) 的整数都可以被分解为有限个素数的乘积：

其中 \(p_1 < p_2 < \cdots < p_m\) 为质数，\(c_i \in \Z^+\) 。

质因子分解

试除法

枚举 \(i \in [2,\sqrt n]\) ，一个一个除尽质因子。当然，最后至多留一个 \(> \sqrt n\) 的质因子，需要特判。

质因子不会太多（最多几十个），所以空间当作常数。

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

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

提前 \(O(n)\) 预处理素数

时间复杂度 \(O(\frac{\sqrt n}{\ln n})\)

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

void get_pfactor(int n, vector<pair<int, int>> &pfactor) {
    for (int i = 2;i * i <= n;i++) {
        if (!(n % i)) pfactor.push_back({ i,0 });
        while (!(n % i)) n /= i, pfactor.back().second++;
    }
    if (n > 1) pfactor.push_back({ n,1 });//最后可能留一个大于sqrt(n)的质数
}

Pollard-Rho算法

Pollard-Rho算法适用于快速随机找到大数的一个非 \(1\) 因子。基于这个算法，我们可以利用递归快速分解一个大数的质因子，时间复杂度大约相同。

普通试除法的时间复杂度是 \(O(\sqrt n)\) ，对于 long long 范围的大数是不可接受的。

Pollard-Rho的想法产生于生成随机数 \(m \in [2,n-1]\) ，测试 \(\gcd (m,n) = d > 1\) ，来产生因子 \(d\) 的算法。但这种算法的期望复杂度是 \(O(\sqrt n \log n)\) ，比试除法还差，因此Pollard考虑利用生日悖论对随机数作差来碰撞因子。

生日悖论：

在一年有 \(n\) 天的情况下，当房间中约有 \(\sqrt{2n\ln 2}\) 个人时，至少有两个人的生日相同的概率约为 \(50 \%\) 。

更进一步地说，我们在 \([1,n]\) 内随机生成数字，产生第一个重复数字前期望有 \(\sqrt {\dfrac{\pi n}{2}}\) 个数，约为 \(\sqrt n\) 个。

因此，假设 \(n\) 有非 \(1\) 因子 \(d\) ，我们从 \([1,n-1]\) 期望随机抽取 \(\sqrt d\) 个数字后，就能产生两个数 \(i,j\) 满足 \(i - j \equiv 0 \pmod d\) ，即 \(\gcd(i-j,n) = d > 1\) 。所以，产生这样一对数字的期望最差复杂度是 \(O(n^{\frac{1}{4}})\) ，但为了找到这些数字，需要大量互相作差并求 \(\gcd\) ，因此复杂度又回到 \(\sqrt n \log n\) 。

Pollard为了避免这种情况，构造了一种伪随机序列 \(x_n = (x_{n-1}^2 + c) \bmod n\) ，其中起点 \(x_0\) 和常数 \(c\) 是随机在 \([1,n-1]\) 中给定的。这样的作用是，假设 \(n\) 有非 \(1\) 因子 \(d\) ，且序列存在一组数字 \(x_i,x_j\) 满足 \(x_i - x_j \equiv 0 \pmod d\) ，那么 \(x_{i+1} - x_{j+1} \equiv x_i^2 - x_j^2 \equiv (x_i-x_j)(x_i+x_j) \equiv 0 \pmod d\) ，即未来所有距离为 \(i-j\) 的数的差都会产生因子 \(d\) 。

因为这组伪随机序列是模 \(n\) 的，因此一定会产生一个混循环（这也是为什么叫做 \(\text{Rho} \to \rho\) ），所以在环上测一组，相当于测了环上所有组距离 \(i-j\) 的数，于是就不需要两两测试了，期望测 \(n^{\frac{1}{4}}\) 组就够了。

此时期望复杂度是 \(O(n^{\frac{1}{4}} \log n)\) ，我们还希望把 \(\log\) 去掉，因此有了倍增优化。倍增优化的原理是：

若 \(\gcd (m,n) = d > 1\) ，则 \(\gcd(km,n)\geq d,k\in \Z^+\) 。

这意味着我们可以累积计算 \(1,2,4,8,\cdots\) 次差，乘在一起求 \(\gcd\) ，若某次作差产生非 \(1\) 因子，那么乘积一定会产生非 \(1\) 因子，时间复杂度为 \(O(n^{\frac{1}{4}} + \log(n^{\frac{1}{4}})\log n)\) 。但是缺点是，我们倍增到最后可能由于单次积累量太大直接超过期望值太多反而变慢。实际上，我们不需要倍增多少次，假设我们取 \(dis\) 作为一次累积的量，那么复杂度为 \(O(n^{\frac{1}{4}} + \frac{n^{\frac{1}{4}}\log n}{dis})\) ，只要 \(dis \geq \log n\) 就能做到复杂度 \(O(n^{\frac{1}{4}})\) 。在 long long 范围内我们令 \(dis = 128\) 就足够了，我们在倍增的基础上每隔 \(128\) 次检测一次即可，不到 \(128\) 次则在结束时检测。

还有一种优化，Floyd判环算法，用于在进入循环时及时退出不重复跑圈。我们设两个数 \(x,y\) ，每次判断 \(\gcd(|x-y|,n)>1\) ，若没有则令 \(x\) 走一步，\(y\) 走两步。因为每次 \(y\) 多走一步，如果进入环则 \(y\) 一定能追上 \(x\) ，此时退出即可。

但实际上，判环算法的优化是不如倍增算法的（时间大约多一倍），且两者不太好兼容，因此我们一般使用倍增算法，而不使用判环算法。

拥有了Pollard-Rho算法，我们就可以对大数 \(n\) 进行质因子分解，时间复杂度大约也是 \(O(n^{\frac{1}{4}})\) ：

1. 用Miller-Rabin算法判断 \(n\) 是否为素数，如果是直接返回，否则进行下一步。
2. 每次用Pollard-Rho算法获得一个非 \(1\) 的因子 \(d\) ，如果为 \(n\) 就再求一次。
3. 将数分解为 \(\dfrac{n}{d}\) 和 \(d\) 两个数，回到第一步递归进行。

时间复杂度 \(O(n^\frac{1}{4})\)

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

namespace Miller_Rabin {
    template<class T>
    T randint(T l, T r) {
        static mt19937 eng(time(0));
        uniform_int_distribution<T> dis(l, r);
        return dis(eng);
    }
    ll qpow(ll a, ll k, ll P) {
        ll ans = 1;
        while (k) {
            if (k & 1) ans = (__int128_t)ans * a % P;
            k >>= 1;
            a = (__int128_t)a * a % P;
        }
        return ans;
    }
    bool isPrime(ll n, int k = 10) {//8-10次
        if (n == 2) return 1;
        if (n == 1 || !(n & 1)) return 0;
        int r = __builtin_ctzll(n - 1);
        ll m = n - 1 >> r;
        while (k--) {
            ll x = qpow(randint(1LL, n - 1), m, n);
            if (x == 1 || x == n - 1) continue;//直接满足,否则r-1次内必须有n-1
            for (int i = 1;i <= r - 1 && x != 1 && x != n - 1;i++) x = (__int128_t)x * x % n;//二次探测
            if (x != n - 1) return 0;//未经过n-1
        }
        return 1;
    }
}

namespace Pollard_Rho {
    using namespace Miller_Rabin;
    ll one_factor(ll n) {
        ll s, x = randint(1LL, n - 1), c = randint(1LL, n - 1), prod = 1;
        for (int dis = 1;;dis <<= 1) {//路径倍增
            s = x;//固定起点作差
            for (int i = 1;i <= dis;i++) x = ((__int128_t)x * x % n + c) % n;//玄学预循环
            for (int i = 1;i <= dis;i++) {
                x = ((__int128_t)x * x % n + c) % n;
                prod = (__int128_t)prod * abs(x - s) % n;//累积因子
                if (i == dis || i % 128 == 0) {//固定最多128次一判
                    ll d = gcd(prod, n);
                    if (d > 1)return d;
                }
            }
        }
    }
    void get_pfactor(ll n, vector<ll> &pfactor) {
        if (isPrime(n)) {
            pfactor.push_back(n);
            return;
        }
        ll d = n;
        while (d >= n) d = one_factor(n);
        get_pfactor(n / d, pfactor);
        get_pfactor(d, pfactor);
    }
}

因数

因数的定义与基本性质

定义 若整数 \(a,b\) 满足 \(a \mid b\) ，则称 \(a\) 是 \(b\) 的因数（约数，因子），\(b\) 是 \(a\) 的倍数。

我们通常讨论的因数默认为正因数，否则一定会指出。

性质1 \(n\) 的正因数有 \(\prod_{i=1}^{m}(c_i+1)\) 个。

性质2 \(n^k,k \in \Z^+\) 的正因数有 \(\prod_{i=1}^{m}(k \cdot c_i+1)\) 个。

性质3 \(n\) 的正因数和为 \(\prod_{i=1}^{m} \sum_{j=0}^{c_i} p_i^{j}\) 。

性质4 \([1,n]\) 内正因数集合大小约为 \(n \log n\) 。

性质5 \(n\) 的正因数个数上界是 \(2\sqrt n\) 。

但实际上这个边界很宽松， \(10^9\) 内的数，因子数最多有 \(1344\) 个；\(10^{18}\) 内的数，因子数最多有 \(103680\) 个。

性质6 \(n\) 的正因数个数期望约为 \(\ln n\) 。

性质1到3可由唯一分解定理得到，性质4到6则由因数的定义得到，下面提供性质4，5证明。

性质4证明：

类似埃氏筛，枚举每个因子的倍数，共 \(\sum_{i=1}^n \frac{n}{i} \approx n \log n\) 个。

性质5证明：

注意到若 \(n\) 有因子 \(d\) 则一定有因子 \(\dfrac{n}{d}\) ，因此我们枚举在 \([1,\sqrt n]\) 的因子，其余可以对称得到，因此知道 \(2\sqrt n\) 是 \(n\) 的因数上界。

正因数集合的求法

试除法

试除法适用于求单个正整数 \(n\) 的因数集合。

根据性质5及其证明，我们枚举因子 \([1,\sqrt n]\) 即可，因子数上界为 \(2\sqrt n\) 。

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

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

void get_factor(int n, vector<int> &factor) {
    for (int i = 1;i * i <= n;i++) {
        if (!(n % i)) {
            factor.push_back(i);
            if (i != n / i) factor.push_back(n / i);
        }
    }
}

倍数法

倍数法适用于求一个区间 \([1,n]\) 的每个数的因数集合，但不能只求出单个数的因数集合。

根据性质4，时间复杂度是 \(O(\sum_{i=1}^n \frac{n}{i}) \approx O(n \log n)\) 。

此法常用于一些因子相关的求和，如 \(\sum_{i=1}^n \sum_{d \mid i} d\) ， \(\sum_{i=1}^n \sum_{d \mid i} f(d)\) 等。

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

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

const int N = 1e5 + 7;
vector<int> factor[N];
void get_factor(int n) {
    for (int i = 1;i <= n;i++) {
        for (int j = 1;i * j <= n;j++) {
            factor[i * j].push_back(i);
        }
    }
}

最大公因数 \(\gcd\)

\(\gcd\) 的定义与基本性质

定义 对于正整数 \(a,b\) ，若正整数 \(d\) 是满足 \(d \mid a\) 且 \(d \mid b\) 的最大数，则称 \(d\) 为 \(a,b\) 的最大公因数（gcd,Greatest Commom Divisor），记为 \(\gcd(a,b) = d\) 。

约定 任何正整数与 \(0\) 的最大公因数是它本身。

互质的定义 对于正整数 \(a,b\) ，若 \(\gcd(a,b) = 1\) ，则称 \(a,b\) 互质（互素）。

性质1 \(\gcd(a,b) = \gcd(b,a)\) 。

性质2 \(\gcd(a,b) = \gcd(a-b,b)\) ，其中 \(a \geq b\) 。

性质3 \(\gcd(a,b) = \gcd(a \bmod b,b)\) 。

性质4 \(\gcd(ka,kb) = k\gcd(a,b)\) 。

性质5 \(\gcd(a,k) = 1 \Rightarrow \gcd(a,kb) = \gcd(a,b)\) 。

性质6 \(\gcd(k,ab) = 1 \iff \gcd(k,a) = \gcd(k,b) = 1\) 。

性质7 \(\gcd(a,b,c) = \gcd(\gcd(a,b),c)\) 。

性质2证明：

根据整除基本性质8，\(a,b\) 的公因数和 \(a-b,b\) 的公因数相同，因此 \(\gcd\) 也相同。

推论1（性质2和5的推论） \(\gcd(a,b) = 1 \iff \gcd (a+b,a) = \gcd(a+b,b) = 1 \iff \gcd(a+b,ab) = 1\) 。

命题1（推论1的逆否命题的结论） \(a+b \mid ab \Rightarrow \gcd(a+b,ab) \neq 1\) 。

\(\gcd\) 的求法

没有极致的效率要求的话，一般c++17及以上推荐用 std::gcd ，c++14以及更低版本推荐手写 \(\gcd\) 。当然也可以使用 libstdc++ 实现的 __gcd ，但不能处理负数所以不安全，不过打ACM的有数据范围就随便用了。

辗转相除法（欧几里得算法）

利用性质3递归，直到一边为 \(0\) ，另一边则为 \(\gcd\) 。

优点是一行写完，缺点是对较大数字取模会比较慢，对于缺点可以用stein算法替代。

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

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

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

更相减损术（stein算法）

利用性质2、4、7迭代，直到一边减为 \(0\) ，另一边乘上公共二次幂 \(k\) 即为 \(\gcd\) 。

优点是只有加减法和位运算，比取模快。

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

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

ll gcd(ll a, ll b) {
    if (!a || !b) return max(a, b);
    int i = __builtin_ctzll(a), j = __builtin_ctzll(b);
    a >>= i, b >>= j;
    while (1) {
        if (a < b) swap(a, b);
        if (!(a -= b)) break;
        a >>= __builtin_ctzll(a);
    }
    return b << min(i, j);
}

最小公倍数 \(\text{lcm}\)

\(\text{lcm}\) 的定义与基本性质

定义 对于正整数 \(a,b\) ，若正整数 \(m\) 是满足 \(a \mid m\) 且 \(b \mid m\) 的最小数，则称 \(m\) 为 \(a,b\) 的最小公倍数（lcm,Least Commom Multiple），记为 \(\text{lcm}(a,b) = m\) 。

性质1 \(\forall a,b \in \N , \gcd(a,b) \cdot \text{lcm}(a,b) = ab\) 。

性质1可由 \(\gcd,\text{lcm}\) 的指数表示法证明，见下一节。

\(\text {lcm}\) 的求法

一般c++17及以上推荐使用 std::lcm ，c++14及更低版本只能手写。

公式法

利用性质1直接求解。

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

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

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;//先除后乘避免溢出
}

\(\gcd\) 与 \(\text{lcm}\) 的其他性质

\(\gcd\) 和 \(\text{lcm}\) 的指数表示法

设正整数 \(n,m\geq 2\) ，则可以表示为：

其中 \(p_i\) 是质数，\(\alpha_i,\beta_i \in \N\) 。

于是有：

性质1 \(\gcd(F_n,F_m) = F_{\gcd(n,m)}\) ，其中 \(F_i\) 为斐波那契数列。

性质2 斐波那契数列相邻两项，”辗转相除”次数等于“更相减损”次数

性质3 \(\gcd(a^n-b^n,a^m-b^m) = a^{\gcd(n,m)} - b^{\gcd(n,m)}\) ，其中整数 \(a \geq b\geq 0\) ，整数 \(n,m \geq 0\) ， \(\gcd(a,b) = 1\) 。

性质4 \(\gcd(a,b) = 1 \Rightarrow \gcd(a^n,b^m) = 1\) ，其中整数 \(a,b,n,m\geq 0\) 。

性质5

性质6 \((n+1)\text{lcm}(C_n^0,C_n^1,\cdots,C_n^n) = \text{lcm}(1,2,\cdots,n+1)\) ，其中 \(n \in \N\) 。

推论1（性质1的推论） 斐波那契数列相邻两项互素。

斐波那契数列

斐波那契数列的定义与基本性质

定义

性质1 \(\sum_{i=1}^n F_i = F_{n+2} -1\)

性质2 \(\sum_{i=1}^n F_{2i-1} = F_{2n}\)

性质3 \(\sum_{i=1}^n F_{2i} = F_{2n+1}-1\)

性质4 \(\sum_{i=1}^n F_{i}^2 = F_{n}F_{n+1}\)

性质5 \(F_{n+m} = F_{n-1}F_{m-1}+F_nF_m\)

性质6 \(F_n^2 = (-1)^{n-1} + F_{n-1}F_{n+1}\)

性质7 \(F_{2n-1} = F_n^2 - F_{n-2}^2\)

性质8 \(F_n = \dfrac{F_{n-2}+F_{n+2}}{3}\)

性质9 \(\lim\limits_{n\to\infty} \dfrac{F_{n+1}}{F_n} = \dfrac{\sqrt{5}-1}{2}\)

性质10 \(F_n = \dfrac{\bigg(\dfrac{1+\sqrt5}{2} \bigg)^n - \bigg(\dfrac{1-\sqrt5}{2} \bigg)^n}{\sqrt 5}\)