【令人心动的算法】GCD 和 LCM
|
ACM 算法笔记
|
379
|
0

3768 字
|
1.2 小时
本文最后更新于99 天前，其中的信息可能已经过时，如有错误请发送邮件到727189340@qq.com

最大公约数（Greatest Common Divisor，GCD）和最小公倍数（Least Common Multiple，LCM）和整除密切相关，在竞赛中经常出现。

整除

设 $a,b \in \mathbf{Z}$，$a \neq 0$。如果 $\exists q \in \mathbf{Z}$，使得 $b = aq$，那么就说 $b$ 可被 $a$ 整除，记作 $a \mid b$；$b$ 不被 $a$ 整除记作 $a \nmid b$。

性质

  • $a \mid b \Longleftrightarrow -a \mid b \Longleftrightarrow a \mid -b \Longleftrightarrow |a| \mid |b|$
  • $a \mid b \land b \mid c \Longleftrightarrow a \mid c$
  • $a \mid b \land a \mid c \Longleftrightarrow \forall x,y \in \mathbf {Z}, a \mid (xb + yc)$
  • $a \mid b \land b \mid a \Longleftrightarrow b =\pm a$
  • 设 $m \neq 0$，那么 $a \mid b \Longleftrightarrow ma \mid mb$
  • 设 $b \neq 0$，那么 $a \mid b \Longleftrightarrow |a| \leq |b|$
  • 设 $a \neq 0, b = qa + c$，那么 $a \mid b \Longleftrightarrow a \mid c$

GCD（最大公约数）

GCD 定义

整数 $a$ 和 $b$ 的最大公约数是指能够同时整除 $a$ 和 $b$ 的最大整数，记为 $\gcd (a,b)$。

由于性质 $a \mid b \Longleftrightarrow |a| \mid |b|$，显然 $\gcd(a,b) = \gcd(|a|,|b|)$。编码时我们只要关注正整数的最大公约数即可。

GCD 性质

一般性质

  • $\gcd(a,b) = \gcd(b,a)$
  • 若 $a \neq 0$，则 $\gcd(a,0) = \gcd(a,a) = |a|$
  • $\gcd(a,b) = \gcd(a,a+b) = \gcd(a,k \cdot a + b)$
  • 多个整数的最大公约数：$\gcd(a,b,c) = \gcd[\gcd(a,b),c] = \gcd[a,\gcd(b,c)]$
    • 更一般地，$\forall 1 < k < n-1, \gcd[\gcd(a_1,a_2,\cdots,a_k),\gcd(a_{k+1},a_{k+2},\cdots,a_n)]$
  • $\gcd(ka,kb) = k \cdot \gcd(a,b)$
  • $\gcd(a^n,b^n) = \gcd(a,b)^n$
  • 若 $\gcd(a,b) = d$，则 $\gcd(a/d,b/d) = 1$，即 $a/d$ 和 $b/d$ 互质

和互质有关的性质

  • 若 $b \mid ac$ 且 $\gcd(a,b)= 1$，则 $b \mid c$
  • 若 $b \mid c$，$a \mid c$ 且 $\gcd(a,b) = 1$，则 $ab \mid c$
  • 若 $\gcd(a,b) = 1$，则 $\gcd(a,bc) = \gcd(a,c)$
  • 若 $\gcd(a_i,b_j) = 1, \forall 1 \leq i \leq n, 1 \leq j \leq m$，则 $\gcd(\prod_{i=1}^n a_i, \prod_{j=1}^m b_j) = 1$。特别地，若 $\gcd(a,b) = 1$，那么 $\gcd(a^n,b^m) = 1$
  • 对整数 $a_1,a_2,\cdots,a_n$，若 $\exists v \in \mathbf{Z}, \prod_i a_i = v^m$，且 $\forall i \neq j$，$\gcd(a_i,a_j) = 1$，则 $\forall 1 \leq i \leq m$，$\sqrt[m]{a_i} \in \mathbf{Z}$

GCD 程序实现

在 C++17 及以上的版本上，我们可以使用 <numeric> 头文件中的 std::gcd 和 gcd::lcm 来求最大公约数和最小公倍数。下面给出的三种求 GCD 的方式主要用于增加对其底层逻辑的理解。

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

辗转相除法的公式是 $\gcd(a,b) = \gcd(b,a \bmod b)$

证明

设 $a = bk + c$，显然有 $c = a \bmod b$

设 $d \mid a$，$d \mid b$，由 $c = a – bk$ 可以推出 $\dfrac{c}{d} = \dfrac{a}{d} – \dfrac{b}{d} k$

有 $\dfrac{c}{d}$ 是整数，即 $d \mid c$，那么对于 $a,b$ 的公约数，它同样是 $b,c$ 的公约数，即 $b, a \bmod b$ 的公约数。

同理可证，$b, a \bmod b$ 的公约数也是 $a,b$ 的公约数。那么它们的最大公约数也是相同的。

程序实现

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

复杂度

欧几里得算法的时间复杂度为 $O((\log_2 \max(a,b))^3)$。

这主要是因为欧几里得算法中用到了大量的取模运算，而高精度的取模运算比较耗时。如果想要优化这个问题，可以使用更相减损术或 Stein 算法，它们只用到了减法和移位的操作。

更相减损术

更相减损术的算法基于这么一个性质：$\gcd(a,b) = \gcd(a, b \cdot k + a)$，取 $k = -1$，可以得到 $\gcd(a,b) = \gcd(a,a-b)$，同理，我们可以得到：$\gcd(a,b) = \gcd(b,a-b) = \gcd(a,a-b)$

具体的计算步骤是：用较大的数减去较小的数，把所得的差和较小的数比较，然后继续做减法操作，直到减数与差相等为止。

int gcd(int a, int b)
{
    while(a != b)
    {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}

Stein 算法

Stein 算法则是更相减损术的改进，它的优化逻辑如下：

  • $a$ 和 $b$ 都是偶数时，有 $\gcd(a,b) = 2 \gcd(\dfrac{a}{2},\dfrac{b}{2})$。
  • $a$ 和 $b$ 一奇一偶时，假设 $a$ 为偶数。由于若 $\gcd(a,b) = 1$，则 $\gcd(a,bc) = \gcd(a,c)$。显然 $\gcd(b,2) = 1$，那么 $\gcd(b,2a) = \gcd(b,a)$，即 $\gcd(a,b) = \gcd(\dfrac{a}{2},b)$。
  • $a$ 和 $b$ 都是奇数时，继续沿用更相减损术进行求解。
int gcd(int a, int b)
{
    if (a < b)
        return gcd(b,a);
    if (b == 0)
        return a;
    if ((!(a & 1)) && (!(b & 1)))
        return gcd(a >> 1, b >> 1) << 1;
    else if ((a & 1) && (!(b & 1)))
        return gcd(a, b >> 1);
    else if ((!(a & 1) && (b & 1)))
        return gcd(a >> 1, b);
    else
        return gcd(a-b,b);
}

实际上，我们会发现这里还有优化空间：过程中算法的本质是不断地去除 $2$ 这一因子以达到对原更相减损术的优化，那么我们无需进行那么多次递归，先把当前这个数不断除以 $2$ 直到其变为奇数即可。在二进制下，就是去除末尾所有的 $1$。

int gcd(int a, int b)
{
    int i,j;
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    for (i = 0; (a & 1) == 0; i++)
        a >>= 1;
    for (j = 0; (b & 1) == 0; j++)
        b >>= 1;
    i = min(i,j);
    while(true)
    {
        if (a < b)
            swap(a,b);
        if ((a -= b) == 0)
            return b << i;
        while((a & 1) == 0)
            a >>= 1;
    }
    return a;
}

但在极端情况下，如P5435 基于值域预处理的快速 GCD，这种用循环找末尾 $0$ 的方法还是太慢。我们可以借用一些更强大的函数来优化这个过程。

__builtin_ctz() 函数可以返回某个数二进制表示的末尾 $0$ 的数量。

int gcd(int a, int b)
{
    int az = __builtin_ctz(a);
    int bz = __builtin_ctz(b);
    int z = min(az,bz);
    int dif;
    b >>= bz;
    while(a)
    {
        a >>= az;
        dif = b-a;
        az = __builtin_ctz(dif);
        if (a < b)
            b = a;
        if (dif < 0)
            a = -dif;
        else
            a = dif;
    }
    return b << z;
}

总结

值得注意的是，stein 算法虽然书写非常不遍历，但是性能上极其优秀，尤其是对超大整数（指超过 long long 范围下的整数）的求解要比欧几里得算法快很多。很多编译器的 std::gcd 算法本身就使用了 stein 算法。平常在求解一般 GCD 的时候，考虑到编码复杂度和效率，建议直接使用 <numeric> 库中的 std::gcd 或者手写欧几里得算法。

高精度求 GCD

Python 和 Java 语言都自带高精度，能很好地处理大数的 GCD。

例题：P2152 [SDOI2009] SuperGCD

Java 代码

import java.math. *;
import java.util. *;__builtin
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        BigInteger a = in.nextBigInteger();
        BigInteger b = in.nextBigInteger();
        System.out.println(a.gcd(b));
    }
}

Python 代码

import math
a = int(input())
b = int(input())
print(math.gcd(a,b))

LCM（最小公倍数）

$a$ 和 $b$ 的最小公倍数表示为 $\operatorname{lcm}(a,b)$，求法可以由算术基本定理推理得到。

算数基本定理：任何大于 $1$ 的正整数 $n$ 都可以唯一分解为有限个质数的乘积：$n = p_1^{c_1} p_2^{c_2} \cdots p_n^{c_n}$，其中 $c_i$ 都为正整数，$p_i$ 都为质数且它们从小到大排列。

设 $a = p_1^{c_1} p_2^{c_2} \cdots p_n^{c_n}$，$b = p_1^{f_1} p_2^{f_2} \cdots p_n^{f_n}$，那么 $\gcd(a,b) = p_1^{\min(c_1,f_1)}p_2^{\min(c_2,f_2)}\cdots p_n^{\min(c_n,f_n)}$，$\operatorname{lcm}(a,b) = \gcd(a,b) = p_1^{\max(c_1,f_1)}p_2^{\max(c_2,f_2)}\cdots p_n^{\max(c_n,f_n)}$

可以推出 $\gcd(a,b) \operatorname{lcm}(a,b) = ab$，即 $\operatorname{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)}$。在实际编码中，注意要先做乘法再做除法，否则可能有 $a \times b$ 溢出的问题。

裴蜀定理

裴蜀定理是关于 GCD 的一个定理。它指的是如果 $a$ 和 $b$ 均为整数，那么就有整数 $x$ 和 $y$ 使 $ax + by = \gcd(a,b)$。显然它有推论：$a$ 和 $b$ 互质当且仅当存在整数 $x$ 和 $y$ 使得 $ax + by = 1$。

可以这么理解裴蜀定理：对任意 $x$ 和 $y$，$d = ax + by$，$d$ 一定是 $\gcd(a,b)$ 的整数倍。最小的 $d$ 是 $\gcd(a,b)$。

裴蜀定理还可以扩展到 $n$ 个整数的情况。即设 $a_1,a_2,\cdots,a_n$ 是不全为 $0$ 的整数，则存在整数 $x_1,x_2,\cdots,x_n$ 使得 $a_1x_1 + a_2x_2 + \cdots + a_n x_n = \gcd(a_1,a_2,\cdots,a_n)$。

裴蜀定理模板题：P4549 【模板】裴蜀定理

题目描述：给定一个包含 $n$ 个元素的整数序列 $A$，记作 $A_1,A_2,A_3,…,A_n$。

求另一个包含 $n$ 个元素的待定整数序列 $X$，记 $S=\sum\limits_{i=1}^nA_i\times X_i$，使得 $S>0$ 且 $S$ 尽可能的小。

首先看两对数的情况：$A_1 X_1 + A_2 X_2$，它符合裴蜀定理的形式，可以表示为 $\gcd(A_1,A_2)$。同理的，将裴蜀定理扩展到 $n$ 个整数的情况，即求解原数列的 GCD。

#include <iostream>
#include <cctype>

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n;
int ans;

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

int main()
{
    n = read();
    ans = read();
    if (ans < 0)
        ans *= -1;
    for (int i = 2; i <= n; i++)
    {
        int temp = read();
        if (temp < 0)
            temp *= -1;
        ans = gcd(temp, ans);
    }
    printf("%d\n", ans);
    return 0;
}

例题

Luogu P2568 GCD

题目链接：P2568 GCD

题目描述：给定正整数 $n$，求 $1 \leq x,y \leq n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对

我们可以根据题意对其进行进一步的数学抽象：

我们可以根据题意对其进行进一步的数学抽象：

$$
\sum_{p \in \mathbf{prime}} \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i,j) = p]
$$

再对其进行变形：

$$
\sum_{p \in \mathbf{prime}} \sum_{i = 1}^{\lfloor \frac{n}{p} \rfloor} \sum_{j = 1}^{\lfloor \frac{n}{p} \rfloor} [\gcd(i,j) = 1]
$$

继续变形得到：

$$
\sum_{p \in \mathbf{prime}} \left( \sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}\left(2 \sum_{j = 1}^{i} [\gcd(i,j) = 1]\right) -1 \right)
$$

注意由于 $i = j = 1$ 时有重复计数，因此需要减去一。

我们发现，$\sum_{j = 1}^{i} [\gcd(i,j) = 1]$ 其实就表示小于等于 $i$ 中的正整数与 $i$ 互质的数的个数，这其实就是一个欧拉函数。因此可以简化得到：

$$
\sum_{p \in \mathbf{prime}} \left( 2 \sum_{i=1}^{\lfloor \frac{n}{p} \rfloor} \varphi(i) -1 \right)
$$

因此，我们首先线性筛出 $\varphi(i)$ 的值并做前缀和，最后枚举小于等于 $n$ 的整数。

#include <iostream>
#include <cctype>
#include <vector>
#define ll long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 1e7 + 5;

int n;
ll ans;

vector<int> pri;
bool not_prime[maxN];
int phi[maxN];
ll sum[maxN];

void init()
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!not_prime[i])
        {
            pri.push_back(i);
            phi[i] = i - 1;
        }
        for (int u : pri)
        {
            if (i * u > n)
                break;
            not_prime[i * u] = true;
            if (i % u == 0)
            {
                phi[i * u] = phi[i] * u;
                break;
            }
            phi[i * u] = phi[i] * phi[u];
        }
    }
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + phi[i];
}

int main()
{
    n = read();
    init();
    for (int i : pri)
        ans += 2 * sum[n / i] - 1;
    printf("%lld\n", ans);
    return 0;
}

Luogu P2398 GCD SUM

题目链接：P2398 GCD SUM

题目描述：给定正整数 $n$，求 $\sum_{i=1}^n \sum_{j = 1}^n \gcd(i,j)$

显然，$\gcd(i,j)_{max} = \gcd(n,n) = n$

和上题类似，抽象出数学模型：

$$
\sum_{k = 1}^n \sum_{i=1}^n \sum_{j = 1}^n [\gcd(i,j) = k]
$$

同理可以整理为：

$$
\sum_{k=1}^n k \left( 2 \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\varphi(i) -1 \right)
$$

#include <iostream>
#include <cctype>
#include <vector>
#define ll long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 1e5 + 5;

int n;
ll ans;

vector<int> pri;
int phi[maxN];
bool not_prime[maxN];
ll sum[maxN];

void init()
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!not_prime[i])
        {
            pri.push_back(i);
            phi[i] = i - 1;
        }
        for (int u : pri)
        {
            if (i * u > n)
                break;
            not_prime[i * u] = true;
            if (i % u == 0)
            {
                phi[i * u] = phi[i] * u;
                break;
            }
            phi[i * u] = phi[i] * phi[u];
        }
    }
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + phi[i];
}

int main()
{
    n = read();
    init();
    for (int i = 1; i <= n; i++)
        ans += i * (2 * sum[n / i] - 1);
    printf("%lld\n", ans);
    return 0;
}

Luogu P1890 GCD区间

题目链接：P1890 gcd区间

利用动态规划的思想，$\gcd(i,j) = \gcd[\gcd(i,i),\gcd(i+1,j)]$，利用 dp 数组存储答案，预处理即可。

#include <iostream>
#include <cctype>

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 1005;

int n, m;
int L, R;

int dp[maxN][maxN];

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

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        dp[i][i] = read();
    for (int i = n - 1; i >= 1; i--)
        for (int j = i + 1; j <= n; j++)
            dp[i][j] = gcd(dp[i][i], dp[i + 1][j]);
    while (m--)
    {
        L = read(), R = read();
        printf("%d\n", dp[L][R]);
    }
    return 0;
}

Luogu P5435 基于值域预处理的快速 GCD

题目链接：P5435 基于值域预处理的快速 GCD

这道题的本意其实考察如题的一道模板，但是使用改良 stein 算法也能通过。这里给出改良 stein 算法的代码，具体的原理前文已经提到过。

#include <iostream>
#include <cctype>
#define ll long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 5005;
const int mod = 998244353;

int n;
ll ans;
ll num;

int a[maxN], b[maxN];

int gcd(int a, int b)
{
    int az = __builtin_ctz(a);
    int bz = __builtin_ctz(b);
    int z = min(az, bz);
    int dif;
    b >>= bz;
    while (a)
    {
        a >>= az;
        dif = b - a;
        az = __builtin_ctz(dif);
        if (a < b)
            b = a;
        if (dif < 0)
            a = -dif;
        else
            a = dif;
    }
    return b << z;
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i <= n; i++)
        b[i] = read();
    for (int i = 1; i <= n; i++)
    {
        num = i;
        ans = 0;
        for (int j = 1; j <= n; j++)
        {
            ans = (ans + num * gcd(a[i], b[j])) % mod;
            num = (num * i) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Luogu P5436 【XR-2】缘分

题目链接：P5436 【XR-2】缘分

题目描述：给定一个正整数 $n$，求 $1 \leq a,b \leq n$ 的情况下最大的 $\operatorname{lcm}(a,b)$。

显然有 $\operatorname{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)}$，则使得 $ab$ 尽量大而 $\gcd(a,b)$ 尽量小。对于后者，显然当 $a,b$ 互质的时候有 $\gcd(a,b) = 1$ 最小。结合条件，可知 $a,b$ 恰好取 $n,(n-1)$ 的时候有最大值。

#include <iostream>
#include <cctype>
#define ll long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int T;
int n;

int main()
{
    T = read();
    while (T--)
    {
        n = read();
        if (n == 1)
        {
            printf("1\n");
            continue;
        }
        printf("%lld\n", 1ll * n * (n - 1));
    }
    return 0;
}

Luogu P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

题目链接：P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

题目描述：给定两个正整数 $x,y$，求使得 $\gcd(a,b) = x$ 且 $\operatorname{lcm}(a,b) = y$ 的数对 $(a,b)$ 的数量。

显然有 $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab$，不妨枚举 $a$ 并根据这个关系求出 $b$，验证是否满足条件。其中，只需验证是否满足前者即可，因为如果前者满足那么后者也一定满足。同时，注意到如果 $(a,b)$ 成立，那么 $(b,a)$ 也一定成立，所以只需枚举到 $\sqrt{xy}$ 再将答案乘 $2$ 即可。又因为 $x = y$ 时一定有 $a = b$，故此时答案需要减少 $1$。

#include <iostream>
#include <cctype>
#define ll long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int x, y;
ll ans;

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

int main()
{
    x = read(), y = read();
    for (int i = 1; i * i <= x * y; i++)
    {
        int j = (x * y) / i;
        if ((x * y) % i != 0)
            continue;
        if (gcd(i, j) != x)
            continue;
        ans += 2;
    }
    if (x == y)
        ans--;
    printf("%lld\n", ans);
    return 0;
}

Luogu P1414 又是毕业季II

题目链接：P1414 又是毕业季II

题目描述：给定一个序列和一个正整数 $k$，求对于 $1 \leq i \leq k$，分别从这个序列中取 $i$ 个数的最大 GCD 是多少

如果暴力求解，枚举取数的组合，复杂度显然太高。考虑公约数本质上是“所有数都具有的约数”，我们对序列中的每个数都进行分解，统计每个因子出现的次数，大于 $i$ 的次数中最大的数可以被认为就是 $i$ 个数的 GCD。

#include <iostream>
#include <cctype>
#define ll long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int x, y;
ll ans;

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

int main()
{
    x = read(), y = read();
    for (int i = 1; i * i <= x * y; i++)
    {
        int j = (x * y) / i;
        if ((x * y) % i != 0)
            continue;
        if (gcd(i, j) != x)
            continue;
        // cout << i << " " << j << "\n";
        ans += 2;
    }
    if (x == y)
        ans--;
    printf("%lld\n", ans);
    return 0;
}

作者

觉得有帮助的话可以投喂煮啵，助力煮啵过上点外卖不用神卷的生活

本文作者：Flaw_Owl
看到这里的朋友们，作者十分感谢！如果你看到任何写得不清楚或是错误之处，或者是有什么希望看到的课程和内容笔记，欢迎在评论区留言！评论区可以单纯的发表文字，也可以使用 Markdown 语法，你可以参照 Markdown 官方教程发出带有格式的评论。

版权说明：本博客所有文章除特别声明外，均采用CC BY-NC-SA 4.0协议，转载请注明文章地址及作者哦
ACMLCM数论
暂无评论

发送评论 编辑评论




























|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!



上一篇
下一篇 


推荐文章
【令人心动的算法】插头 DP


【令人心动的算法】快速幂


【令人心动的算法】最小生成树


【令人心动的算法】字典树


【令人心动的算法】进制哈希


【令人心动的算法】整除分块


【令人心动的算法】欧拉路


【令人心动的算法】Manacher 算法