GCD 题集

SUNCHAOYI · 2024-12-26 18:46:54 · 算法·理论

• \gcd (x,y)

求两个数 x,y(x > y) 的最大公因数，辗转相除法即可。

int gcd (int x,int y){return !y ? x : gcd (y,x % y);}

• \rm lcm(x,y)

求两个数 x,y(x > y) 的最小公倍数，即求 \dfrac{xy}{\gcd (x,y)} 的值，证明如下：

令 k = \gcd (x,y)，则有 \gcd (\frac{x}{k},\frac{y}{k}) = 1；
对于两个互质的数来说，最小公倍数即为两数的乘积，所以有 \rm lcm(x,y) = \dfrac{xy}{\gcd (x,y)}。

• P2568 GCD

给定正整数 n，求 1\le x,y\le n 且 \gcd(x,y) 为素数的数对 (x,y) 有多少对。

题目即求 \displaystyle \sum_{k \in prime} \sum_{i = 1}^{n} \sum_{j = 1}^{n} [\gcd (i,j) = k]。

对于 i,j 满足 \gcd (i,j) = k，则有 \gcd (\dfrac{i}{k},\dfrac{j}{k}) = 1。所以说，原式等价于：

容易想到欧拉函数的定义，直接转换可得：

于是这道题只需要先预处理处 \varphi(i)就能在 O(n) 解决。同时，用欧拉函数预处理出质数，然后在统计时答案应为：

显然，对于一个合法的素数对 (i,j)， (j,i) 一定也满足条件，但是如果 i = j，则需要去重。

• P2398 GCD SUM

和上一题有一定的联系，直接推式子：

对于 \lfloor \dfrac{n}{k} \rfloor 的处理，直接分块就能在 O(\sqrt n) 的时间复杂度下搞定。于是乎，直接预处理即可使整一程序达到 O(n) 的时间复杂度。

• Shohag Loves XOR (Easy Version)

题意： 给定 x,m，求有多少 y 满足 y \in [1,m],x \neq y 且 x \oplus y 是 x 或 y 的因子。

结论猜测：x \oplus y \in [1,x)，下面是证明：

对于一个 p 的因子 f，满足 f \le \lfloor \frac{p}{2} \rfloor，也就是说 f 和 p 在二进制下的最高位不同。

当 y \ge 2x 时，x \oplus y 与 y 在二进制下的最高位相同，所以 x \oplus y 在此时必定不是 y 的因子。同时，由于最高位的不同，此时 x \oplus y > x 一定成立，所以 x \oplus y 同样也不是 x 的因子。

所以说，只有 y < 2x 时，才能满足题意，也就是说因子 x \oplus y < x。

• Shohag Loves XOR (Hard Version)

给定 x,m，求有多少 y 满足 y \in [1,m] 使得 x \oplus y 可以被 x 或 y 整除。

设 p = x \oplus y，分三种情况讨论：

• GCD等于XOR

题意： 求 \sum_{x=1}^{n}\sum_{y=1}^{n}[\gcd(x,y)=(x\oplus y)]。

若 x = y，答案显然成立。下面令 x > y，设 x = \gcd(x,y) \times x',y = \gcd(x,y) \times y'。同时，注意到异或特有的性质 x - y \le x \oplus y \le x + y，则可列出不等式：

于是当 \gcd (x,y) = x \oplus y 成立时当且仅当 \gcd (x,y) = x \oplus y = x - y。因此枚举预处理即可。

• Shohag Loves GCD

题意： 从给定集合中选数并构造序列 \{a_i\}，需要满足 a_{\gcd (i,j)} \neq \gcd(a_i,a_j) \mid \forall 1 \le i < j \le n 并且构造出的序列字典序最大。

不妨从反面分析，考虑满足 a_{\gcd (i,j)} = \gcd (a_i,a_j)。当 i \mid j 时，\gcd (i,j) = i，a_i \mid a_j。进一步的，当 i \nmid j 时，是否也存在一个 i，满足 a_{\gcd (i,j)} = \gcd (a_i,a_j) 呢？

假设存在这个 i，我们设 g = \gcd (i,j)，那么 a_g = \gcd (a_i,a_j) 且 g < i。由于 g \mid i，等价于 g = \gcd (g,i)，由上面的结论可知 a_{\gcd (g,i)} = \gcd (a_g,a_i)。此时与题目的条件不符合，故假设不成立。

GCD Guess

题意： 每次询问 a,b 返回 \gcd (x + a,x + b) 的值，最终求出 x。

由数据范围不难想到按位考虑。

在二进制条件下，设最低位为第 0 位。目前要猜测第 i 位的值，设 t 表示前 i - 1 位所贡献的值。令 a < b，则有（加粗表示第 i 位）：

由公式 \gcd (t + a,t + b) = \gcd (t + a,b - a) 可知（加粗表示第 i 位）：

此时 \gcd (t + a,b - a) = 2^i。当实际 x 的第 i 位为 1 时，会产生 2 次进位，使得 \gcd (t' + a,b - a) = 2^{i + 1}。因此可以得到以下代码：

for (int i = 0;i < 30;++i)//猜测第 i 位 
{
    int ans = query ((1 << i) - x,(1 << i) + (1 << (i + 1)) - x);
    if (ans == 1 << (i + 1)) x |= 1 << i;
}

• Guess Numbers

题意： 每次询问 (a,b)，返回 \gcd (x + a,y + b) 的值，求出 x,y。

先用 (0,0),(0,1),(1,0) 最多三次即可确定最低位。之后先将最低 x 位全部弄成 1（相当于每次询问的时候取反），然后 +1 即可变为全为 0 的形式，并将当前询问位取反。用类似的方式，每一位最多三次即可得到答案。

void solve ()
{
    ll x = 0,y = 0,dx = 0,dy = 0;
    ll g = query (0,0);
    if (g % 2 == 0) dx |= 1,dy |= 1;
    else 
    {
        g = query (1,0);
        if (g % 2 == 0) x |= 1,dy |= 1;
        else
        {
            g = query (0,1);
            if (g % 2 == 0) y |= 1,dx |= 1;
            else x |= 1,y |= 1;
        }
    }
    ll b = 1;
    for (int i = 1;i < 60;++i)
    {
        g = query (dx + 1,dy + 1);
        if ((g >> b) % 2 == 0) x |= 1ll << i,y |= 1ll << i;
        else
        {
            g = query (dx + 1 + (1ll << i),dy + 1);
            if ((g >> b) % 2 == 0) dx |= 1ll << i,y |= 1ll << i;
            else
            {
                g = query (dx + 1,dy + 1 + (1ll << i));
                if ((g >> b) % 2 == 0) dy |= 1ll << i,x |= 1ll << i;
                else dx |= 1ll << i,dy |= 1ll << i;
            }
        }
        ++b;
    }
    printf ("! %lld %lld\n",x,y);fflush (stdout);
}

• Maximum modulo equality

题意： 对于一个询问 [l,r]，找到最大的 m 满足 \forall i,j \in [l,r]，均满足 a_i \mod m = a_j \mod m。

条件转换成 |a_i - a_j| \mod m = 0，因此对于一个询问，在形成差分后维护区间的 \gcd 即可。

• Coprime Pair 同 Problem about GCD 【后者为复杂版本】

题意： 找到 l,r \in [x,y] 满足 \gcd (l,r) = g 且 r - l + 1 尽可能的大的一对（若答案仍不唯一，取 l 最小的。

先给结论：先将其转换为前者的题目 \gcd (l,r) = 1 的情况，然后直接暴力枚举 l,r 之间的差值以及 l 的值，前者从大到小枚举，后者从小到大，找到后就直接 break。

听着有点荒谬，但确实不会超时。于是就有了这个问题：

虽然题目和互质数相关，但是显然可以归约到 Prime Gap 问题上来。目前数学界的猜测是 \ln 级别，相关文献 Prime Gap。