# command_block 的博客

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

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

$$\sum\limits_{i=1}^n\sum_{j=1}^mq(ij)$$

\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}

$$q_d(p^k)=[p|d][k\bmod 2=0]p^{ck/2}+[p\!\!\not|\ d]p^{c\lfloor k/2\rfloor}$$

• 当 $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]$ 。

\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}

\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}