command_block 的博客

command_block 的博客

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

posted on 2021-11-23 19:23:03 | under 记录 |

确实是难以复刻的好题,今天看来,对过气的数论仿佛有了一点希望。

官方题解见 UOJ Long Round #1 题解 ,这里介绍一下参赛大佬们提出的更简洁的做法。

题意 : 给出常数 $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})$ 。