HDUOJ 6434 - Count

Author Avatar
Jimmy Zhang Aug 23, 2018
  • Read this article on other devices

题面

本题有 TT 个询问,对于每个询问 nn,你需要计算:

i=1nj=1i1[gcd(i+j,ij)=1]\sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{i - 1} \left[ \gcd(i + j, i - j) = 1 \right]

数据范围

1T1051 \le T \le 10^5

1n2×1071 \le n \le 2 \times 10^7

题目链接

分析

题意就是要求满足 1j<in1 \le j < i \le ngcd(i+j,ij)=1\gcd(i + j, i - j) = 1(i,j)(i, j) 对个数。

首先 gcd(i+j,ij)\gcd(i + j, i - j) 并不直观,我们考虑令 k=ijk = i - j,则有 k[1,i1]k \in [1, i - 1],以及:

i=1nj=1i1[gcd(i+j,ij)=1]=i=1nk=1i1[gcd(2ik,k)=1]=i=1nk=1i1[gcd(2i,k)=1]\begin{aligned}
& \sum\limits_{i = 1}^{n} \sum\limits_{j = 1}^{i - 1} \left[ \gcd(i + j, i - j) = 1 \right] \
& = \sum\limits_{i = 1}^{n} \sum\limits_{k = 1}^{i - 1} \left[ \gcd(2i - k, k) = 1 \right] \
& = \sum\limits_{i = 1}^{n} \sum\limits_{k = 1}^{i - 1} \left[ \gcd(2i, k) = 1 \right] \
\end{aligned}

首先当 kk 是偶数时显然 gcd(2i,k)1\gcd(2i, k) \neq 1,故 kk 只可能是奇数。由此,gcd(2i,k)=1\gcd(2i, k) = 1gcd(i,k)=1\gcd(i, k) = 1 等价。

我们知道欧拉函数 φ(i)\varphi(i) 即表示 [1,i)[1, i) 中与 ii 互质的自然数的个数,由此:

  • ii 是奇数,我们需要去除 φ(i)\varphi(i) 中包含的偶数,则答案为 12φ(i)\frac{1}{2} \cdot \varphi(i)(不严谨解释见后文);
  • ii 是偶数,则 φ(i)\varphi(i) 中不可能包含偶数,则答案即 φ(i)\varphi(i)

即:

k=1i1[gcd(i,k)=1]=φ(i)1+(imod2)\sum\limits_{k = 1}^{i - 1} \left[ \gcd(i, k) = 1 \right] = \frac{\varphi(i)}{1 + (i \bmod 2)}

我们记:

g(i)=φ(i)1+(imod2)g(i) = \frac{\varphi(i)}{1 + (i \bmod 2)}

则原式即:

i=1ng(i)\sum\limits_{i = 1}^{n} g(i)

预处理出 g(i)g(i) 的前缀和并 O(1)\mathcal{O}(1) 回答每个询问即可。


顺便不严谨地阐述一下为什么 ii 是奇数时答案为 12φ(i)\frac{1}{2} \cdot \varphi(i)

首先我们知道 [1,i1][1, i -1] 显然时奇偶各占一半的。要证 [1,i1][1, i - 1] 中与 ii 互质的数奇偶各占一半,只需要证明 [1,i1][1, i - 1] 中与 ii 不互质的数中就各占一半。

考虑将 ii 表示为:

i=p1k1p2k2pnkni = p_1^{k_1} \cdot p_2^{k_2} \cdots p_n^{k_n}

其中 pi2p_i \neq 2

由此一来,我们可以将所有小于 ii 且与 ii 不互质的数表示为:

p1, 2p1, , (p2k2p3k3pnkn1)p1p2, 2p2, , (p1k1p3k3pnkn1)p2pn, 2pn, , (p1k1p2k2pn1kn11)pn\begin{aligned}
& p_1, \ 2p_1, \ \dots, \ (p_2{k_2}p_3{k_3} \cdots p_n^{k_n} - 1)p_1 \
& p_2, \ 2p_2, \ \dots, \ (p_1{k_1}p_3{k_3} \cdots p_n^{k_n} - 1)p_2 \
& \dots \
& p_n, \ 2p_n, \ \dots, \ (p_1{k_1}p_2{k_2} \cdots p_{n-1}^{k_{n-1}} - 1)p_n
\end{aligned}

首先对于每一行都是奇数偶数各占一半的。当然上面列举的数中显然是有重复的。若把上面 nn 行看作 nn 个集合,那么任意 nn 个集合并起来后得到的集合依然是奇偶各占一半。那么全集显然也是奇偶各占一半。

实现

借助线性筛,我们可以在 O(N)\mathcal{O}(N) 的复杂度内初始化欧拉函数,同时我们也可以在 O(N)O(N) 时间内初始化 g(n)g(n) 的前缀和。初始化好后再对不同询问进行 O(1)\mathcal{O}(1) 回答即可。

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/08/23/hduoj-6434/