2.18 数论题

目前咕咕咕：T6 T8 以及 T5 的 魔改 Min25 。

T1

$T\le 5000,a,b\le 10^9$ 求：

$\sum_{i=a}^b \text{lcm}(i,b) \bmod 10^9 + 7$

前缀和一下即求

$\sum_{i=1}^n \text{lcm}(i,b)$

有一种曾经卷老师教过的非常不错的推法，考虑求和 $\gcd$ 的时候可以直接转乘 $\varphi$ ，

$\begin{aligned} & \sum_{i=1}^n \gcd(i,n)\\ &= \sum_{i=1}^n \sum_{k|\gcd(i,n)} \varphi(k) \end{aligned}$

原因是

$\sum_{a|b} \varphi(a) = b$

那么考虑这个题，我们求

$b\sum_{i=1}^n \frac{i}{\gcd(i,b)}$

我们可以定义一个函数 $f$ ，类似之前的 $\varphi$ 来做

$\sum_{a|b} f(a) = \frac 1 b\\ f \times I = \{\frac 1 x\}\\ f = \{\frac 1 x\} \times \mu$

然后就有

$\begin{aligned} &=b \sum_{i=1}^n i \sum_{d | \gcd(i,b)} f(d)\\ &=b\sum_{d|b} f(d) \sum_{i=1}^{n/d} di\\ &= b\sum_{d|b} f(d)d S(\frac n d) \end{aligned}$

那么 $f$ 到底是啥？显然 $f$ 是个积性函数。那么有 $f(1) = 1$ 。

$f(p) + f(1) = \frac 1 p\\ f(p^2) + f(p) + f(1) = \frac 1 {p^2}$

有

$f(p) = \frac 1 p - 1\\ f(p^k) = \frac{1}{p^k} - \frac{1}{p^{k-1}} = \frac{1}{p^k}(1-p)\\ f(n) = \frac 1 n (1-p_1)(1-p_2) \cdots$

复杂度 $O(T\sqrt n)$ 。

T2

$1 \le a \le b \le 10^{10}$ 求：

$\sum_{i=a}^b \frac 1 i \sum_{j=1}^i \text{lcm}(i,j)$

显然可以拆前缀和。于是就成了

$\begin{aligned} &\sum_{i=1}^n \frac 1 i \sum_{j=1}^i \text{lcm}(i,j)\\ =&\sum_{i=1}^n \sum_{j=1}^i \frac j {\gcd(i,j)}\\ =&\sum_{i=1}^n \sum_{j=1}^i \sum_{t=1}^n [\gcd(i,j) = t] \frac j {t}\\ =&\sum_{t=1}^n \frac 1 t \sum_{i=1}^n \sum_{j=1}^i [\gcd(i,j) = t] j\\ =&\sum_{t=1}^n \sum_{i=1}^{n/t} \sum_{j=1}^i [\gcd(i,j) = t] j\\ \end{aligned}$

然后考虑

$\begin{aligned} &\sum_{i=1}^n [\gcd(i,n) = 1] i\\ =& \sum_{i=0}^n [\gcd(i,n) = 1] i - [n=1] \end{aligned}$

然后暂时不管后面那个 $[n=1]$ ，显然可以枚举一下 $(n-i)$ ，而且由于 $\gcd(i,n) = \gcd(n-i,i)$ ，所以有

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

然后两式相加，有

$= \frac{n\varphi(n) + [n=1]}{2}$

所以继续推，就是

$\frac 1 2\left(n+\sum_{t=1}^n \sum_{i=1}^{n/t} i\varphi(i)\right)$

后面那坨东西显然是可以杜教筛的，具体来说，我们有

$\sum_{pq = i} \varphi(p) = i\\ \sum_{pq=i} p\varphi(p) q = i^2$

然后可以方便地求出 $n/t$ 处的值。

T3

$n \le 10^{12}$ 求：

$\begin{aligned} &\sum_{i=1}^n \sum_{d|i}\gcd(d,\frac i d)\\ =&\sum_{i=1}^n \sum_{d|i} \sum_{k|\gcd(d,\frac i d)} \varphi(k)\\ =&\sum_{k=1}^n \varphi(k) G(k) \end{aligned}$

其中 $G(k)$ 表示统计有多少对 $(i,d)$ 满足 $d|i,k|d,k|\frac i d$ 。

因为 $d$ 是 $k$ 的倍数可以考虑枚举 $d$ ，那么 $i$ 的限制即是 $kd | i$ 。

$\sum_{k=1}^n \varphi(k) \sum_{d=1}^{n/k} \lfloor \frac n {dk^2} \rfloor$

这个东西的时间复杂度是什么？显然当 $k > \sqrt n$ 的时候是没有值的。那么 $k$ 只需要枚举到 $\sqrt n$ ，后面这个东西可以考虑对 $\frac{n}{k^2}$ 来数论分块，复杂度即是

$\sum_{k=1}^{\sqrt n} \sqrt{\frac{n}{k^2}} = O(\sqrt n \log n)$

对于后面的东西，按照 $\frac n k$ 记忆化即可做到 $O(\sqrt n)$ 。

T4

仔细考虑这个 $f$ 的定义，不难发现实际上求的是

$f(x) = \prod p_i^{e_i/2}$

也就是

$f(x) = g(x)\\$

$g(x)$ 是 $x$ 的最大平方因子开根后的结果。

这个题的原题推法非常仙，就不写了（而且也不太可能想的到），这里写一下 lsj 秒的推法。设 $u = g(x)$ ，那么显然对于 $x$ 的任何平方因子 $d^2$，一定有 $d|u$ ，且所有 $u$ 的约数都一定能满足这个数的平方是 $x$ 的因子。

于是我们考虑进行一种容斥，这个容斥计算了所有 $u$ 的约数且最后结果整好是 $u$ ，即

$\sum_{d | u} f(d) = u$

显然 $f = \varphi$ 即可。所以对于一个数有

$g(x) = \sum_{d^2 | x} \varphi(d)$

那么我们要计算的就是

\sum_{i=1}^n \sum_{d^2|i} \varphi(d)\\ = \sum_{d=1}^\sqrt n \varphi(d) \lfloor\frac{n}{d^2}\rfloor

于是复杂度就是 $O(\sqrt n)$ 了。

然后这题还有一个更 NB 的做法（同时让我第一次学了学 Powerful Number）。在 这里 写了一下。

T5

显然的，设 $f(x)$ 为 $x$ 除以 $x$ 的最小质因子，那么原题即求

$\begin{aligned} &\sum_{i=1}^n \sum_{j=1}^n f(\gcd(i,j))^k\\ =&\sum_{t=1}^n f(t)^k \sum_{i=1}^{n/d} \sum_{j=1}^{n/d} [\gcd(i,j) = 1]\\ =&\sum_{t=1}^n f(t)^k \left(\sum_{i=1}^{n/d} (2\varphi(i)) - 1\right) \end{aligned}$

后面这部分，显然是可以一次杜教筛解决的。

考虑前面这个东西怎么解决。考虑 $f$ 的定义，是一个数除以它的最小质因子，

这个可以魔改 Min_25 筛来解决。具体来说，将记录答案的时候添加一维 $0/1$ 表示是否已经除过了最小质因子。具体实现细节等以后写题再补吧（

T7

给定 $x,a,b$ ，求 $(i,j)$ 对数满足

i <= a && j <= b && x / i * j == x * j / i

$T \le 20 , x,a,b \le 10^9$

显然这个得把下取整转取模

$\sum_{i=1}^a \sum_{j=1}^b [j\frac{x - x\bmod i}{i} = \frac{xj - xj \bmod i}{i}]\\ \sum_{i=1}^a \sum_{j=1}^b [j(x\bmod i) = xj \bmod i]\\ \sum_{i=1}^a \sum_{j=1}^b [j(x \bmod i) < i]\\ \sum_{i=1}^a \min\{\lceil \frac i {x \bmod i}\rceil - 1,b\}$

如果 $i > x$ ，就算的是

$\sum_{i=x+1}^a \min\{\lceil \frac i x\rceil - 1 , b\}$

显然算一下哪个位置前面小于 $b$ 即可。

否则算的就是

$\sum_{i=1}^x \min\{\lceil \frac i {x - \lfloor\frac x i\rfloor i} \rceil,b\}$

我们考虑根据 $\lfloor \frac x i \rfloor$ 和外面的 $\lceil \frac i {x - \lfloor\frac x i\rfloor i} \rceil$ 的值的改变来进行分块。打表会发现 $x=10^9$ 仅有约 $7\times 10^5$ 段。因此可以通过本题。

详细证明可以见官方题解。