gcd 最大公约数


  • 欧几里得算法

    1、求两个数的最大公约数,除了分解质因数法,我们通常使用欧几里得算法(即辗转相除法),其思路如下
    2、求m,n 的最大公约数,就计算 m / n,然后m = nn = m % n,继续循环计算。直到n = 0时停止,这时的m就是最大公约数;或者提前一步,到m % n == 0(结果余数为 0)时停止,这时的n就是最大公约数(推荐后者,在写拓展欧几里得算法时更方便)
    3、gcd 的性质gcd(a, b) = gcd(a, k*a+b)gcd(k*a, k*b) = k * gcd(a, b)a / gcd(a, b)b / gcd(a, b)互素多个整数最大公约数gcd(a, b, c) = gcd(gcd(a, b), c);a 大于 b 时,gcd(a, b) = gcd(a, b-a)

  • 代码实现

    // 循环写法
    int gcd(int m, int n)
    {
        int temp;
        while (m % n)
        {
            temp = m % n;
            m = n;
            n = temp;
        }
        return n;
    }
    
    // 递归写法
    int gcd(int m, int n)
    {
        return (m % n) ? gcd(n, m % n) : n;
    }

lcm 最小公倍数


  • 公式法

    1、求两个数的最小公倍数,除了分解质因数法,我们通常使用公式法,其思路如下
    2、求m,n 的最小公倍数,有gcd(m, n) * lcm(m, n) = m * n,所以得到公式lcm(m, n) = m * n / gcd(m, n)

  • 代码实现

    // 最大公约数
    int gcd(int m, int n)
    {
        int temp;
        while (m % n)
        {
            temp = m % n;
            m = n;
            n = temp;
        }
        return n;
    }
    
    // 最小公倍数
    int lcm(int m, int n)
    {
        return m * n / gcd(m, n);
    }

拓展欧几里得算法


  • 拓展欧几里得算法

    1、裴蜀定理(最大公约数表示定理):设整数 a, b最大公约数gcd(a, b)d,则必然存在整数 s, t 使得as + bt = d;特别地,当gcd(a, b) = 1(即 a, b 互素),必然有as + bt = 1。在此基础上有推论:如果d | v(d 是 v 的因子),那么也有 s, t 使得as + bt = v = kd逆向推导亦然,如果存在这样的 s, t,那么d 必然是 v 的因子
    2、与裴蜀定理相关的,有拓展欧几里得算法,其是用来计算as + bt = gcd(a, b)中的 s 和 t 的。该算法的本质是:在执行欧几里得算法的过程中,利用每一步计算出来的余数和副产品——,顺道通过迭代公式计算出每一步的 s, t最后一步(实际是倒数第二步)求得的 s, t,便是所求的 s, t
    3、其中迭代公式为:si+1 = si-1 - si * qi , ti+1 = ti-1 - ti * qi ,其中 q 为商,且 s0 = 1,s1 = 0,t0 = 0,t1 = 1
    4、举例说明:有a = 100, b = 35,则有100 * s + 35 * t = gcd(100, 35) = 5,其执行拓展欧几里得算法的过程如下表。算法最后得到gcd(100, 35) = 5,且有 s = s3 = -1t = t3 = 3满足裴蜀定理

    轮次 被除数 a 除数 b 商 q 余数 si+1 = si-1 - si * qi ti+1 = ti-1 - ti * qi
    1 100 35 2 30 s2 = 1 - 0 * 2 = 1 t2 = 0 - 1 * 2 = -2
    2 35 30 1 5 s3 = 0 - 1 * 1 = -1 t3 = 1 - (-2) * 1 = 3
    3 30 5 6 0
  • 代码实现

    #include <cstdio>
    #include <iostream>
    using namespace std;
    
    // 循环写法
    int ex_gcd(int a, int b, int &s, int &t)
    {
        // s, t 表示 s_i 和 t_i,其默认值为 s_1 = 0 和 t_1 = 1
        // s_ 和 t_ 表示 s_i-1 和 t_i-1,其默认值表示 s_0 = 1 和 t_0 = 0
        int s_ = 1, t_ = 0, q, temp;
        while (a % b)
        {
            q = a / b;
    
            // 迭代公式:s_i+1 = s_i-1 - s_i * q_i
            temp = s;       // 记录当前 s_i
            s = s_ - s * q; // 计算 s_i+1
            s_ = temp;      // 下一轮 s_i
            // 迭代公式计算 t_i+1
            temp = t;
            t = t_ - t * q;
            t_ = temp;
    
            temp = a % b;
            a = b;
            b = temp;
        }
        return b;
    }
    
    // 递归写法
    int ex_gcd(int a, int b, int &s, int &t)
    {
        if (b == 0)
        {
            s = 1, t = 0;
            return a;
        }
    
        int gcd = ex_gcd(b, a % b, t, s);
        t -= (a / b) * s;
        return gcd;
    }
    
    int main()
    {
        // s, t 表示 s_i 和 t_i,其默认值为 s_1 = 0 和 t_1 = 1
        int a, b, s = 0, t = 1;
        cin >> a >> b;
        int gcd = ex_gcd(a, b, s, t);
        printf("%d(a) * %d(s) + %d(b) * %d(t) = %d(gcd(a, b))", a, s, b, t, gcd);
        return 0;
    }

唯一分解定理


  • 唯一分解定理

    1、内容:任意一个大于 1 的自然数 N,都可以表示为有限个质数的乘积。即:N = P1a1 + P2a2 + P3a3 + …,其中 Pi质数,ai指数。例如 12 = 22 * 31
    2、有关正因数个数:对于大于 1 的自然数 N,其正因数的个数为:ct = (1 + a1) * (1 + a2) * (1 + a3) * … * (1 + an)
    3、有关 gcd 和 lcm:通过唯一分解定理可表示 gcd(a, b) = P1min(a1,b1) + P2min(a2,b2) + P3min(a3,b3) + …; lcm(a, b) = P1max(a1,b1) + P2max(a2,b2) + P3max(a3,b3) + …

  • 区间 lcm

    1、区间 lcm:给定 l 和 r(都不超过 40000),输出[l, r]区间内所有数最小公倍数,结果对 109 + 7 取模
    2、由上结论得:解决此问题,只需要通过唯一分解定理,对[l, r]间的数分解质因数,并分别记录所有质因子最大指数,最后再将所有质因子相乘
    3、代码实现时,要先通过质数筛筛选范围内的所有质数;再依次分解质因数,分别记录质因子最大指数,注意最后需要特判;为优化最后质因子相乘的效率,通过快速幂实现相乘
    4、同理可得,对于区间 gcd,只需要记录所有质因子最小指数,但记录的数组需要提前初始化为无穷,并在最后相乘时判断只相乘出现过的质因子(数量不为无穷的质因子)

  • 代码实现

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 4e4 + 10;
    const int P = 1e9 + 7;
    
    vector<int> prime;
    bitset<N> not_prime;
    int cnt[N]; // 表示 lcm 的指数
    
    // 快速幂取模
    long long ModExp(long long a, long long b)
    {
        long long res = 1;
        while (b)
        {
            if (b & 1)
                res = res * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return res;
    }
    
    // 欧拉线性筛
    void oler(int n)
    {
        for (int i = 2; i <= n; i++)
        {
            if (!not_prime[i])
                prime.push_back(i);
    
            for (int j = 0; prime[j] * i <= n; j++)
            {
                not_prime[prime[j] * i] = true;
                if (i % prime[j] == 0)
                    break;
            }
        }
    }
    
    // 唯一分解定理:质因数分解
    void func(int n)
    {
        for (int i = 2; i <= n / i; i++)
        {
            // 如果 n 能整除 i,说明 i 不是 n 的质因子
            if (n % i)
                continue;
    
            int tmp = 0;  // 记录质因子的指数
            while (n % i == 0)
            {
                n /= i;
                tmp++;
            }
            cnt[i] = max(cnt[i], tmp);  // 记录质因子 i 的最大指数
        }
    
        // 特判 n 为质数(此时 n > 1)的情况
        if (n > 1)
            cnt[n] = max(cnt[n], 1);
    }
    
    void solve()
    {
        oler(4e4);
    
        int l, r;
        cin >> l >> r;
        for (int i = l; i <= r; i++)
            func(i);
    
        long long ans = 1;
        // 相乘所有质因子,得到 lcm
        for (int i = 2; i <= r; i++)
        {
            if (!not_prime[i])
                ans = ans * ModExp(i, cnt[i]) % P;
        }
        cout << ans;
    }
    
    int main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int T = 1;
        // cin >> T;
        while (T--)
            solve();
        return 0;
    }

页底评论