GCD 题集

$\gcd (x,y)$

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

1	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$。所以说，原式等价于：

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

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

$\sum_{i = 1}^{\lfloor \dfrac{n}{k}\rfloor} \sum_{j = 1}^{\lfloor \dfrac{n}{k}\rfloor} [\gcd (\frac{i}{k},\frac{j}{k}) = 1] = \sum_{i = 1}^{\lfloor \dfrac{n}{k}\rfloor} \varphi (i)$

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

$\displaystyle \sum_{k \in prime} (2 \times \sum_{i = 1}^{\lfloor \dfrac{n}{k}\rfloor} \varphi (i) - 1)$

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

P2398 GCD SUM

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

$\displaystyle \sum_{i = 1}^{n} \sum_{j = 1}^{n} \gcd (i,j)\\ = \sum_{k = 1}^{n} \sum_{i = 1}^{n} \sum_{j = 1}^{n} k [\gcd (i,j) = k]\\ = \sum_{k = 1}^{n} (k \sum_{i = 1}^{n} \sum_{j = 1}^{n} [\gcd (i,j) = k])\\ = \sum_{k = 1}^{n} (k \sum_{i = 1}^{n} \sum_{j = 1}^{n} [\gcd (\dfrac{i}{k},\dfrac{j}{k}) = 1])\\ 令 x = \dfrac{i}{k},y = \dfrac{j}{k}\\ 原式 = \sum_{k = 1}^{n} (k \sum_{i = 1}^{n} \sum_{j = 1}^{n} [\gcd (x,y) = 1])\\ = \sum_{k = 1}^{n} (k \sum_{i = 1}^{\lfloor \dfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \dfrac{n}{k} \rfloor} [\gcd (x,y) = 1])\\ = \sum_{k = 1}^{n} (k \sum_{i = 1}^{\lfloor \dfrac{n}{k} \rfloor} \varphi (i))\\$

对于 $\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$，分三种情况讨论：

$x | p$。设 $p = kx$，则 $y = x \oplus p \le p + x \le m$，也就是 $kx \le m - x$，进一步化简可知 $k \le \lfloor \frac{m - x}{x} \rfloor$。由于我们还有 $(m - x,m]$ 区间未检测，但可以充分利用 $x \oplus y \le x + y$ 这个性质，我们循环判断 $(m - x,m + x]$ 区间即可（当然，官方解答的做法更加简洁，但是没看懂）。
$y | p$。当 $0 < x < y$ 时，$p \le x + y < y + y = 2y$，因此 $p = ky(k \ge 2)$ 不存在解。因此只需要考虑 $y \le x$ 的情况。
$x | p$ 且 $y | p$。当 $x \neq y$ 时，$\rm{lcm(x,y)} \ge 2 \max (x,y)$，然而 $p < 2 \max (x,y)$，因此只有 $x = 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) \le \gcd (x,y) \times (x'-y') \le 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$ 位）：

$\begin{cases} t + a \text{ changes to } \quad \textbf{1}0\cdots 0\\ t + b \text{ changes to } 1\textbf{1}0\cdots 0\ \end{cases}$

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

$\begin{cases} t + a \text{ changes to } \quad \textbf{1}0\cdots 0\\ b - a \text{ changes to } 1\textbf{0}00\cdots 0\ \end{cases}$

此时 $\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);
}