[数论记录]Uoj#578. 【ULR #1】校验码

确实是难以复刻的好题，今天看来，对过气的数论仿佛有了一点希望。 官方题解见 [UOJ Long Round #1 题解](https://skip2004.blog.uoj.ac/blog/6532) ，这里介绍一下参赛大佬们提出的更简洁的做法。 **题意** ： 给出常数 $c$ ，定义积性函数 $q(p^k)=p^{c\lfloor k/2\rfloor}$ 。 给出 $n,m$ ，求下列式子的值： $$\sum\limits_{i=1}^n\sum_{j=1}^mq(ij)$$ 答案对 $2^{32}$ 取模。 多组数据，$T\leq 3,n\leq 5\times 10^5,m\leq 1.2\times 10^{11}$ ，时限$\texttt{5s}$。 ------------ 记积性函数 $f(p^k)=p^{k\bmod 2}$ ，则有 $q(ij)=q(i)q(j)\gcd(f(i),f(j))^c$ 。 记 $g=\mu*id_c$ ，可以用 $g$ 反演掉 $\gcd(a,b)^c$ 。 $$ \begin{aligned} &\sum\limits_{i=1}^n\sum_{j=1}^mq(ij)\\ =&\sum\limits_{i=1}^n\sum_{j=1}^mq(i)q(j)\gcd(f(i),f(j))^c\\ =&\sum\limits_{i=1}^n\sum_{j=1}^mq(i)q(j)\sum\limits_{d|f(i),d|f(j)}g(d)\\ =&\sum\limits_{d=1}^ng(d)\sum\limits_{d|f(i),1\leq i\leq n}q(i)\sum\limits_{d|f(j),1\leq j\leq m}q(j)\\ =&\sum\limits_{d=1}^ng(d)S(n,d)S(m,d)\\ \end{aligned} $$ 其中 $S(n,d)=\sum\limits_{d|f(i),1\leq i\leq n}q(i)$ 。 只需要求出 $S(n,1\sim n),S(m,1\sim n)$ 即可。 可以发现 $f(i)|i$ ，所以所有 $d|f(i)$ 的 $i$ 都必须满足 $d|i$ 。 则有 $S(n,d)=\sum\limits_{1\leq i\leq \lfloor n/d\rfloor}[d|f(id)]q(id)$ 。 由于 $d|f(id)$ ，说明 $d$ 是一个无平方因子数，且 $d$ 的素因子在 $i$ 中的次数都是偶数。因此，有 $q(id)=q(i)$。 记 $q_d(n)=[d|f(nd)]q(n)$ ，则有 $S(n,d)=\sum\limits_{1\leq i\leq \lfloor n/d\rfloor}q_d(i)$ 。 可以发现， $q_d$ 是个积性函数（$[d|f(nd)],q(n)$ 分别积性，点乘仍然有积性），观察质数幂处的取值： $$q_d(p^k)=[p|d][k\bmod 2=0]p^{ck/2}+[p\!\!\not|\ d]p^{c\lfloor k/2\rfloor}$$ 注意到 $q_d$ 和 $q$ 只有 $d$ 倍数处的位置取值值不同，可以计算 $w_d=q_d/q$ 。 - 当 $k=1$ 时， $w_d(p)+q(p)=q_d(p)=[p\!\!\not|\ d]p^{c\lfloor k/2\rfloor}$ ，则 $w_d(p)=-[p|q]$ - 当 $k=2$ 时， $w_d(p^2)+q(p^2)+w_d(p)q(p)=q_d(p^2)=p^{c}$ ，则 $w_d(p^2)=[p|q]$ 。 - 当 $k=3$ 时， $w_d(p^3)+q(p^3)+w_d(p^2)q(p)+w_d(p)q(p^2)=q_d(p^3)=p^c$ ，则 $w_d(p^3)=-[p|q]$ 。 如此反复，可归纳证明 $w_d(p^k)=[p|d](-1)^k$ 。 则有 ： $$ \begin{aligned} S(n,d)&=\sum\limits_{1\leq i\leq \lfloor n/d\rfloor}q_d(i)\\ &=\sum\limits_{1\leq i\leq \lfloor n/d\rfloor}\sum\limits_{j|i}w(j)q(i/j)\\ &=\sum\limits_{j=1}^{\lfloor n/d\rfloor}w_d(j)\sum\limits_{j|i}^{\lfloor n/d\rfloor}q(i/j)\\ &=\sum\limits_{j=1}^{\lfloor n/d\rfloor}w_d(j)\sum\limits_{i=1}^{\lfloor n/dj\rfloor}q(i) \end{aligned} $$ 注意到 $w_d$ 有值的位置不多（不足 $3\times 10^7$），可以暴力搜索出所有有值的位置。 那么问题就变为求出 $q$ 的块筛（或称基本和组），官方题解中有 $O(m^{3/5})$ 的做法。 下面也有一个 $O(m^{3/5})$ 的做法，会更简洁一些 ： 首先显然有 $q(p)=1$ ，根据 PN 相关理论，可以 $O(m^{3/5})$ 求块筛。 具体地，构造 $h=q/I$ ，则 $h$ 只在 PN 处有值。 不仅如此，可以证明 $h(p^k)=[k\bmod 2=0]\Big(p^{ce/2}-p^{c(e/2-1)}\Big)$ ，$h$ 只在平方数处有值。 记 $h_2(n)=h(n^2)$ ，则 $$ \begin{aligned} S_q(n)=&\sum\limits_{i=1}^nq(i)\\ =&\sum\limits_{i=1}^n\sum\limits_{j|i}h(j)\\ =&\sum\limits_{j=1}^nh(j)\lfloor n/j\rfloor\\ =&\sum\limits_{j=1}^{\lfloor \sqrt{n}\rfloor }h_2(j)\lfloor n/j^2\rfloor\\ \end{aligned} $$ 用线性筛求出 $O(\sqrt{m})$ 内的 $h_2$ 函数，然后可以整除分块 $O(n^{1/3})$ 计算一个 $S_q(n)$ 。 若要求块筛，根线性筛复杂度平衡一下可以做到 $O(m^{3/5})$ 。