「Summary」2022-07-15 做题记录

脑壳痛 的 第一天。

2022-07-14

$\mathbb{CF235E}$

link
给定 $a, b, c$ 求 $\sum_{i = 1}^{a}\sum_{j = 1}^{b}\sum_{k = 1}^{c} d(i j k)$ ，对 $2^{30}$ 取模。
记得原来学杜教筛的时候记过一个结论 $d(ij) = \sum_{x \mid i}\sum_{y \mid j} [\gcd(x, y) = 1]$ 。但是这里是三个数的乘积，不妨合并其中两个，令 $t = ij$ ，得到是 $d(tk) = \sum_{x \mid t}\sum_{y \mid k} [\gcd(x, y) = 1]$ ，看得出来 $x$ 是 $ij$ 的因子，设 $x = x_i \times x_j, x_i\mid i, x_j \mid j$ ，而要满足 $\gcd(x, y) = 1$ 的条件只能是 $\gcd(x_i, k) = \gcd(x_j, k) = 1$ 。因为 $a, b, c$ 是有轮换关系的，所以可以轻松得到 $d(i j k) = \sum_{x \mid i} \sum_{y \mid j} \sum_{z \mid k} [\gcd(x, y) = \gcd(x, z) = \gcd(y, z) = 1]$ 。
要求的式子变成
$$ \sum_{i = 1}^{a}\sum_{j = 1}^{b}\sum_{k = 1}^{c} d(i j k) \\ = \sum_{i = 1}^{a}\sum_{j = 1}^{b}\sum_{k = 1}^{c} \sum_{x \mid i} \sum_{y \mid j} \sum_{z \mid k} [\gcd(x, y) = \gcd(x, k) = \gcd(y, k) = 1] $$
改变枚举顺序，得到
$$ \sum_{x = 1}^{a} \sum_{y = 1}^{b} \sum_{z = 1}^{c} [\gcd(x, y) = \gcd(x, z) = \gcd(y, z) = 1] \times \lfloor \frac{a}{x} \rfloor \lfloor \frac{b}{y} \rfloor \lfloor \frac{c}{z} \rfloor $$
继续利用科技手段反演 $[\gcd(i, j) = 1] = \sum_{d | \gcd(i, j)} \mu(d)$ ，尝试大力出奇迹。
$$ \sum_{x = 1}^{a} \sum_{y = 1}^{b} \sum_{z = 1}^{c} \sum_{d_1 \mid \gcd(x, y)}\mu(d_1) \sum_{d_2 \mid \gcd(x, y)}\mu(d_2) \sum_{d_3 \mid \gcd(x, y)}\mu(d_3) \times \lfloor \frac{a}{x} \rfloor \lfloor \frac{b}{y} \rfloor \lfloor \frac{c}{z} \rfloor $$
然而看起来很🤮。如果只先反演一个 $\gcd$ ，应该会得到
$$ \sum_{x = 1}^{a} \sum_{y = 1}^{b} \sum_{z = 1}^{c} \sum_{d_1 \mid \gcd(x, y)}\mu(d_1) [\gcd(x,z) = 1, \gcd(y, z) = 1] \times \lfloor \frac{a}{x} \rfloor \lfloor \frac{b}{y} \rfloor \lfloor \frac{c}{z} \rfloor $$
改变枚举顺序，得到
$$ {\sum_{d}\mu(d) \sum_{i}^{\lfloor \frac{a}{d} \rfloor} \sum_{j}^{\lfloor \frac{b}{d} \rfloor} \sum_{z = 1}^{c} [\gcd(id,z) = 1, \gcd(jd, z) = 1] \times \lfloor \frac{a}{id} \rfloor \lfloor \frac{b}{jd} \rfloor \lfloor \frac{c}{z} \rfloor} $$
进一步地
$$ \sum_{z = 1}^{c} \lfloor \frac{c}{z} \rfloor {\sum_{d}^{\min\{a, b\}}\mu(d) \sum_{i}^{\lfloor \frac{a}{d} \rfloor} [\gcd(id, z) = 1] \lfloor \frac{a}{id} \rfloor \sum_{j}^{\lfloor \frac{b}{d} \rfloor} [\gcd(jd, z) = 1] \lfloor \frac{b}{jd} \rfloor} $$
发现可以做了？🤡
然后搞笑的是想了 0.5h 的初始化。。。

$\mathbb{BZOJ4407}$

link
$$ \begin{aligned} & \sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k \\ = & \sum_{g = 1}^{\min(n, m)} g^k \sum_{i=1}^{\lfloor \frac{n}{g} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{g} \rfloor} [\gcd(i, j) = 1] \\ = & \sum_{g}^{\min(n, m)} g^k \sum_{i=1}^{\lfloor \frac{n}{g} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{g} \rfloor} \sum_{d \mid \gcd(i, j)} \mu(d) \\ = & \sum_{d=1}^{\min(n, m)} \sum_{t = 1}^{\lfloor \frac{n}{d} \rfloor} dt^k \sum_{i=1}^{\lfloor \frac{n}{dt} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{dt} \rfloor} \sum_{d \mid \gcd(i, j)} \mu(d) \\ \end{aligned} $$

令 $T = dt$ 。

$$ \begin{aligned} & = \sum_{T = 1}^{\min(n, m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d \mid T} d^k \mu(\frac{T}{d}) \\ & = \sum_{T = 1}^{\min(n, m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d \mid T} id_k(d) \mu(\frac{T}{d}) \\ \end{aligned} $$

令 $f(T) = \sum_{d \mid T} id_k(d) \mu(\frac{T}{d})$。
$$ \begin{aligned} f(n) & = f(\prod p_i ^ {x_i}) \\ & = \prod f(p_i^{x_i}) \\ f(p_i^{x_i}) &= \sum_{j = 1}^{x_i} id_k(p_i^j) \times \mu(p_i^{x_i - j}) \\ &= f(p_i^{x_i})\times \mu(1) + f(p_i^{x_i - 1})\times\mu(p_i) \\ &= (p_i^k - 1)\times p_i^{k\times (x_i - 1)} \end{aligned} $$
然后《发现》递推关系: $f(p_i^{x_i}) = f(p_i^{x_i - 1}) \times p_i^k$ 。
当 $x_i = 1$ 时，$f(p_i) = p_i^k - 1$ 。

在线性筛的时候，首先得到 $f(i)$ ，目前要求 $f(i \times p_j)$ 。

$\mathbb{CF542D}$

link
这个函数如此扭曲。。。
$$ J(x) = \sum_{1 \le k \le x, k \mid x, [\gcd(k, x / k) = 1]} k $$
有唯一分解定理 $x = p_1^{e_1} p_2^{e_2} p_3^{e3} ...$ 如果有贡献，那么每个质因子一定是最高次幂。
对于 $x$ ，$J(x) = \prod{(p_i^{e_i} + 1)}$ ，问题就变成求 $A = \prod{(p_i^{e_i} + 1)}$ 的解的个数。
这玩意儿怎么反解啊。。。

---

嗯，看了题解，会了。
可以大力搜索，首先《发现》每个质数 $p_i^{e_i} + 1$ 只会被枚举一遍，考虑从小到大枚。
设 $f(i, A)$ 表示用从 $i$ 到 $+\infin$ 的质因子凑出 $A$ 的方案数。
当质因子小于 $\sqrt n$ 可以搜索，当质因子大于 $\sqrt n$ 的特殊考虑。
具体地说，如果 $p^2 + 1 > A > p + 1$ ，此时可以直接判断 $A - 1$ 是不是质数。