• (数论) 除法取模(求逆元)

    文章目录

    前言

    在四则运算的取模中，加减乘可以在取模时候任意交换和结合，而除法不但不能，还不使用最基本的A/B都不能直接mod

    因此需要用到数论中的逆元，本文讲介绍三种处理方式

    一般多数题目的mod是一个素数，因此费马小定理用的比较多，也是必须掌握的模板

    本题后面还拓展了部分与逆元相关的常用知识点

    除法取模 -> 求逆元

    前提：A/B可以整除

    下面三行公式即为什么要从除法取模化为逆元

    ( A / B ) ( m o d p ) ( A ∗ B − 1 ) ( m o d p ) 即核心为求 B ( m o d p ) 的逆元 ( B ∗ B − 1 ) ≡ 1 ( m o d p ) (A / B) \pmod p \\ (A * B^{-1}) \pmod p \\ 即核心为求B \pmod p的逆元 \\ (B * B^{-1}) \equiv 1 \pmod p (A/B)(modp)(A∗B−1)(modp)即核心为求B(modp)的逆元(B∗B−1)≡1(modp)

    除法取模

    练习题：A/B - 1576

    Problem Description

    要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

    Input

    数据的第一行是一个T，表示有T组数据。
    每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

    Output

    对应每组数据输出(A/B)%9973。

    费马小定理

    费马小定理_百度百科 (baidu.com)

    费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有 a p − 1 ≡ 1 ( m o d p ) {a^{p-1}\equiv 1 \pmod p} ap−1≡1(modp)。

    重点： p 是一个质数 a p − 1 ≡ 1 ( m o d p ) a ∗ a p − 2 ≡ 1 ( m o d p ) 重点：p是一个质数 \\ a^{p-1} \equiv 1 \pmod p \\ a * a^{p-2} \equiv 1 \pmod p 重点：p是一个质数ap−1≡1(modp)a∗ap−2≡1(modp)

    /**
 * https://acm.hdu.edu.cn/showproblem.php?pid=1576
 * A/B
 */
#include 
using namespace std;
#define int long long

// 9973是一个素数
const int mod = 9973;

/**
 * molecular 分子
 * denominator 分母
 */
int subMod(int molecular, int denominator, int mod) {
    // 快速幂
    function<int(int, int, int)> binPow = [](int base, int expo,
                                             int mod) -> int {
        int ans = 1;
        base %= mod;
        if (expo == 0) {
            ans = 1 % mod;
        } else {
            while (expo) {
                if (expo & 1) {
                    ans = ans * base % mod;
                }
                base = base * base % mod;
                expo >>= 1;
            }
        }
        return ans;
    };

    // 求B^-1
    // B * B^-1 = 1 (mod p) (p为素数)
    // B * B^{p-2} = 1 (mod p) (费马小定理)
    int inverseElement = binPow(denominator, mod - 2, mod);
    // A/B
    // A*B^-1
    return (molecular * inverseElement) % mod;
}

void solve() {
    int a, b;
    cin >> a >> b;
    cout << subMod(a, b, mod) << endl;
}

signed main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    扩展gcd求逆元

    专题：(数论) 扩展gcd_天赐细莲的博客-CSDN博客

    欧几里德算法扩展_百度百科 (baidu.com)

    裴蜀定理_百度百科 (baidu.com)

    这是一种求逆元的通用方式
    ( a ∗ a − 1 ) ≡ 1 ( m o d b ) ( a ∗ a − 1 ) + ( b ∗ b − 1 ) ≡ 1 根据贝祖定理，下式比成立 ( a ∗ a − 1 ) + ( b ∗ b − 1 ) ≡ g c d ( a , b ) (a * a^{-1}) \equiv 1 \pmod b \\ (a * a^{-1}) + (b * b^{-1})\equiv 1 \\ 根据贝祖定理，下式比成立 \\ (a * a^{-1}) + (b * b^{-1})\equiv gcd(a, b) (a∗a−1)≡1(modb)(a∗a−1)+(b∗b−1)≡1根据贝祖定理，下式比成立(a∗a−1)+(b∗b−1)≡gcd(a,b)

    /**
 * https://acm.hdu.edu.cn/showproblem.php?pid=1576
 * A/B
 */
#include 
using namespace std;
#define int long long

// 9973是一个素数
const int mod = 9973;

// 扩展gcd模板
int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int xx, yy;
    int d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - a / b * yy;
    return d;
}

/**
 * molecular 分子
 * denominator 分母
 * 扩展gcd求逆元不需要mod是一个素数
 * (a*x) * (b*y) = 1
 * 此时x是a(mod b)的逆元
 */
int subMod(int molecular, int denominator, int mod) {
    int x, y;
    // x是b的逆元，y是mod的逆元
    // 但此时是针对等式右侧为gcd
    // ax + by = gcd
    // 目的是等式右侧为1
    // 因此等式两边同除gcd
    int GCD = exgcd(denominator, mod, x, y);
    // x化为正数
    x = ((x % mod) + mod) % mod;
    int inverseElement = x / GCD;
    return (molecular * inverseElement) % mod;
}

void solve() {
    int a, b;
    cin >> a >> b;
    cout << subMod(a, b, mod) << endl;
}

signed main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60

    欧拉定理

    欧拉定理_百度百科 (baidu.com)

    欧拉函数_百度百科 (baidu.com)

    费马小定理是欧拉定理的一个特例

    欧拉函数： [ 1 , n ] 中与 n 互质的数的个数，计为 φ ( n ) φ ( n ) = n ∗ ∏ i = 1 s p i − 1 p i ( p i 为 n 的质因子 ) 欧拉函数：[1, n]中与n互质的数的个数，计为φ(n) \\ φ(n) = n * \prod^{s}_{i=1}{ \frac{p_i - 1}{p_i}} (p_i为n的质因子) 欧拉函数：[1,n]中与n互质的数的个数，计为φ(n)φ(n)=n∗i=1∏s​pi​pi​−1​(pi​为n的质因子)

    欧拉定理：若 g c d ( a , p ) ≡ 1 ( m o d p ) 则 a φ ( p ) ≡ 1 其中 φ ( p ) 是 p 的欧拉函数 欧拉定理：若gcd(a, p) \equiv 1 \pmod p \\ 则 a^{φ(p)} \equiv 1其中φ(p)是p的欧拉函数 欧拉定理：若gcd(a,p)≡1(modp)则aφ(p)≡1其中φ(p)是p的欧拉函数

    /**
 * https://acm.hdu.edu.cn/showproblem.php?pid=1576
 * A/B
 */
#include 
using namespace std;
#define int long long

// 9973是一个素数
const int mod = 9973;

// 欧拉函数 => 求[1, n]中与n互质的数的个数
// φ(n) = n * Π{(pi - 1) / pi}
// 其中pi是n的质因子
int getPhi(int n) {
    // 别忘了有个n的贡献
    int ans = n;
    // 唯一分解定理
    for (int i = 2; i * i <= n; i += 1) {
        if (n % i == 0) {
            // 先除后乘防溢出
            ans = ans / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    // 超出 √n的质因数
    if (n > 1) {
        ans = ans / n * (n - 1);
    }
    return ans;
}
// 扩展欧拉定理 (欧拉降幂)
// 求 a^b (mod m)
//   - a^b                      (b <  φ(m)) (mod m)
//   - a^{b mod φ(m) + φ(m)}    (b >= φ(m)) (mod m)

// 欧拉定理
// gcd(a, m) = 1
// 则 a^φ(m) = 1 (mod m)
int EulerFunction(int n, int mod) {
    // 快速幂
    function<int(int, int, int)> binPow = [](int base, int expo,
                                             int mod) -> int {
        int ans = 1;
        base %= mod;
        if (expo == 0) {
            ans = 1 % mod;
        } else {
            while (expo) {
                if (expo & 1) {
                    ans = ans * base % mod;
                }
                base = base * base % mod;
                expo >>= 1;
            }
        }
        return ans;
    };

    // 化为 gcd(a, m) = 1
    // 题目保证了这里的gcd为1
    // 若不为1则需将a,m除以gcd(先判断能否整除)
    // int GCD = __gcd(n, mod);
    // 这里算的是mod的值
    int phi = getPhi(mod);

    // a^φ(m) = 1 (mod m)
    // a * a^{φ(m)-1} = 1 (mod m)
    return binPow(n, phi - 1, mod);
}

/**
 * molecular 分子
 * denominator 分母
 * 欧拉定理求逆元
 */
int subMod(int molecular, int denominator, int mod) {
    int inverseElement = EulerFunction(denominator, mod);
    return (molecular * inverseElement) % mod;
}

void solve() {
    int a, b;
    cin >> a >> b;
    cout << subMod(a, b, mod) << endl;
}

signed main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    拓展

    这个拓展部分不做过多的文字说明，因为都是大量的公式推到

    大多数核心内容均在代码中用注释的方式表示

    欧拉线性筛

    前置知识：欧拉素数筛

    专题：(数论) 从判断素数到素数筛

    杭电：The Euler function - 2824

    /**
 * https://acm.hdu.edu.cn/showproblem.php?pid=2824
 * The Euler function
 * ===============================================
 * 欧拉函数：n以内的gcd为1的个数
 * 借助欧拉筛线性求欧拉函数
 */
#include 
using namespace std;

class EulerFunction {
public:
    vector<int> phi;

private:
    int n;
    vector<bool> vis;
    vector<int> prime;

public:
    EulerFunction(int n) {
        this->n = n;
        EulerSieve();
    }

protected:
    // 欧拉函数的三个性质
    // 1. p为质数 phi(p) = p - 1
    // 2. p为质数 phi(p^k) = (p - 1) * p^{k-1}
    // 3. 积性函数 f(nm) = f(n) * f(m)

    // 欧拉筛，线性求欧拉函数值
    void EulerSieve() {
        phi = vector<int>(n + 1);
        // false 素数
        // true 合数
        vis = vector<bool>(n + 1);
        prime.clear();

        // 1的欧拉函数视为1
        phi[1] = 1;
        for (int i = 2; i <= n; i += 1) {
            if (!vis[i]) {
                prime.push_back(i);
                // i为素数，则phi为i-1
                phi[i] = i - 1;
            }
            // 借助最小质因子来筛掉合数
            for (int j = 0; prime[j] * i <= n; j += 1) {
                int num = prime[j] * i;
                // 标记为合数
                vis[num] = true;

                // 欧拉晒筛的核心，每个合数只筛一次
                if (i % prime[j] == 0) {
                    // phi(m) = m * Π((p-1)/p)
                    // phi(m) = 素 * i * Π((p-1)/p)
                    // phi(m) = 素 * phi(i)
                    // phi[m] = pj * phi[i]
                    phi[num] = phi[i] * prime[j];
                    break;
                } else {
                    // 积性函数 f(nm) = f(n) * f(m)
                    // ∵ m = i * 素
                    // ∴ phi(m) = phi(i) * phi(素)
                    // ∴ phi(m) = phi(i) * (素 - 1)
                    // 即：phi[m] = phi[i] * (pj - 1)
                    phi[num] = phi[i] * (prime[j] - 1);
                }
            }
        }
    }
};

signed main() {
    const int M = 10 + 3000000;
    EulerFunction ef(M);
    vector<int>& phi = ef.phi;

    int left, right;
    while (~scanf("%d %d", &left, &right)) {
        // 可以再算一个前缀和优化一下
        long long sum = 0;
        for (int i = left; i <= right; i += 1) {
            sum += phi[i];
        }
        printf("%lld\n", sum);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91

    扩展欧拉定理

    扩欧又名欧拉降幂，主要作用是大数的幂运算进行降幂的操作

    洛谷：P5091 【模板】扩展欧拉定理

    力扣：372. 超级次方

    class EXEulerTheorem {
public:
    int eulerPower(int base, vector<int>& expoList, int mod) {
        int phi = getPhi(mod);
        int expo = dePow(expoList, phi);
        return binPow(base, expo, mod);
    }

    int eulerPower(int base, const string& s, int mod) {
        vector<int> expoList;
        for (char ch : s) {
            expoList.push_back(ch + '0');
        }
        return eulerPower(base, expoList, mod);
    }

    int eulerPower(int base, char* s, int mod) {
        vector<int> expoList;
        for (int i = 0; s[i] != '\0'; i += 1) {
            expoList.push_back(s[i] + '0');
        }
        return eulerPower(base, expoList, mod);
    }

    int eulerPower(int base, int expo, int mod) {
        return eulerPower(base, to_string(expo), mod);
    }

private:
    // 欧拉函数 => 求[1, n]中与n互质的数的个数
    // φ(n) = n * Π{(pi - 1) / pi}
    // 其中pi是n的质因子
    int getPhi(int n) {
        // 别忘了有个n的贡献
        int ans = n;
        for (int i = 2; i * i <= n; i += 1) {
            if (n % i == 0) {
                // 先除后乘防溢出
                ans = ans / i * (i - 1);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        // 超出 √n的质因数
        if (n > 1) {
            ans = ans / n * (n - 1);
        }
        return ans;
    }

    // 欧拉定理
    // gcd(a, m) = 1
    // 则 a^φ(m) = 1 (mod m)

    // 扩展欧拉定理 (欧拉降幂)
    // 求 a^b (mod m)
    //   - a^b                      (b <  φ(m)) (mod m)
    //   - a^{b mod φ(m) + φ(m)}    (b >= φ(m)) (mod m)
    int dePow(vector<int>& expoList, int phi) {
        int expo = 0;
        bool flag = false;
        for (int i = 0; i < expoList.size(); i += 1) {
            // 秦九韶 算法累计成整数
            expo = expo * 10 + expoList[i];
            // 扩展欧拉定理的核心
            if (expo >= phi) {
                expo %= phi;
                flag = true;
            }
        }
        // - b < φ(n)
        //  a^b
        // - b >= φ(n)
        //  a^{b mod φ(n) + φ(n)}
        if (flag) {
            expo += phi;
        }
        return expo;
    }

    // 常规快速幂
    int binPow(int base, int expo, int mod) {
        int ans = 1;
        base %= mod;
        if (expo == 0) {
            ans = 1 % mod;
        } else {
            while (expo) {
                if (expo & 1) {
                    ans = ans * base % mod;
                }
                base = base * base % mod;
                expo >>= 1;
            }
        }
        return ans;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99

    线性求逆元

    洛谷：P3811 【模板】乘法逆元

    题目描述

    给定 n , p n,p n,p 求 1 ∼ n 1\sim n 1∼n 中所有整数在模 p p p 意义下的乘法逆元。

    这里 a a a 模 p p p 的乘法逆元定义为 a x ≡ 1 ( m o d p ) ax \equiv 1\pmod p ax≡1(modp) 的解。

    线性求逆元并没有用到扩展gcd，但是往往是一个由扩展gcd拓展出来的问题（就像费马小定理一样）

    证明：设求第i个数的逆元
    设 p ≡ k ∗ i + r ( p 为素数， k 为倍数， i 为要求第几个数的逆元， r 为余数 ) 变形 k ∗ i + r ≡ 0 ( m o d p ) 两边同时乘 i − 1 和 r − 1 构造出 i − 1 k ∗ r − 1 + i − 1 ≡ 0 ( m o d p ) 移项 i − 1 ≡ − k ∗ r − 1 ( m o d p ) 用 p 和 i 表示倍数 k 和余数 r { k = p / i r = p % i i − 1 ≡ − ⌊ p / i ⌋ ∗ ( p % i ) − 1 ( m o d p ) 设 \quad p \equiv k * i + r \quad (p为素数，k为倍数，i为要求第几个数的逆元，r为余数) \\ 变形 \quad k * i + r \equiv 0 \pmod p \\ 两边同时乘 i^{-1} 和 r^{-1} 构造出i^{-1} \\ k * r^{-1} + i^{-1} \equiv 0 \pmod p \\ 移项 \quad i^{-1} \equiv - k * r^{-1} \pmod p \\ 用p和i表示倍数k和余数r

    {k=p/ir=p%i" role="presentation">{k=p/ir=p%i
    \\ i^{-1} \equiv - \lfloor p / i \rfloor * (p \% i)^{-1} \pmod p 设p≡k∗i+r(p为素数，k为倍数，i为要求第几个数的逆元，r为余数)变形k∗i+r≡0(modp)两边同时乘i−1和r−1构造出i−1k∗r−1+i−1≡0(modp)移项i−1≡−k∗r−1(modp)用p和i表示倍数k和余数r{k=p/ir=p%i​i−1≡−⌊p/i⌋∗(p%i)−1(modp)

    /**
 * https://www.luogu.com.cn/problem/P3811
 * P3811 【模板】乘法逆元
 * 线性求逆元
 */
#include 
using namespace std;
#define int long long

signed main() {
    int n, p;
    scanf("%lld %lld", &n, &p);

    // i^-1 = -floor(p/i) * (p%i)^-1 % p
    vector<int> inv(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; i += 1) {
        // p/i化为正数
        inv[i] = (p - (p / i)) * inv[p % i] % p;
    }

    for (int i = 1; i <= n; i += 1) {
        printf("%lld\n", inv[i]);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    END

  • 相关阅读:
    JAVA自定义注解
    未来智能汽车数字化转型之路必不可少强大的高级排产软件
    华为鸿蒙4谷歌GMS安装教学
    Linux tips: shell中启动多进程并行批处理的技巧
    基于Java springMVC+MySQL的大学校园BBS论坛网站设计与实现
    计算机毕业设计Java新城街道社区的健康档案管理平台(源码+系统+mysql数据库+Lw文档）
    table的展开折叠按钮操作
    04-jQuery动画
    【Redis学习笔记】第三章 Redis通用指令
    PTA_乙级_1006
  • 原文地址：https://blog.csdn.net/CUBE_lotus/article/details/127592783