Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

Solution「国家集训队 JZPKIL」

posted on 2021-04-15 13:54:05 | under 题解 |

今天心情不好,所以又来做数论题了......


题目大意

$$\sum_{i=1}^n\text{g.c.d}^x(i,n)\text{l.c.m}^y(i,n)$$ 的值.

其中$n\le10^{18},x,y\le 3000$.

题解

根据基本套路先推一波式子$$\begin{aligned}\sum_{i=1}^n\text{g.c.d}^n(i,n)\text{l.c.m}^y(i,n)&=n^y\sum_{i=1}^ni^y\text{g.c.d}^{x-y}(i,n)\\&=n^y\sum_{d|n}d^{x-y}\sum_{i=1}^ni^y[\text{g.c.d}(i,n)=d]\\&=n^y\sum_{d|n}d^{x-y}\sum_{i=1}^{n/d}(id)^y[i\perp n]\\&=n^y\sum_{d|n}d^{x}\sum_{i=1}^{n/d}i^y[i\perp n]\end{aligned}$$ 第二个和式就是「一个人的数论」,写过了的读者可以跳过下面这一部分

令$$S(n)=\sum_{i=1}^ni^y[i\perp n]$$ 则有$$\begin{aligned}S(n)&=\sum_{i=1}^ni^y\sum_{k|i,k|n}\mu(k)\\&=\sum_{k|n}\mu(k)\sum_{i=1}^{n/k}(ik)^y\\&=\sum_{k|n}\mu(k)k^y\sum_{i=1}^{n/k}i^y\\&=\sum_{k|n}\mu(k)k^y\sum_{i=1}^{y+1}a_i\left(\frac{n}{k}\right)^i\\&=\sum_{i=1}^{y+1}a_i\sum_{k|n}\mu(k)k^{y}\left(\frac{n}{k}\right)^i\end{aligned}$$

回到主线,代回原式得$$\begin{aligned}n^y\sum_{d|n}d^{x}\sum_{i=1}^{n/d}i^y[i\perp n]&=n^y\sum_{d|n}d^x\sum_{i=1}^{y+1}a_i\sum_{kd|n}\mu(k)k^y\left(\frac{n}{kd}\right)^i\\&=n^y\sum_{i=1}^{y+1}a_i\sum_{d|n}d^x\sum_{kd|n}\mu(k)k^y\left(\frac{n}{kd}\right)^i\\&=n^y\sum_{i=1}^{y+1}a_i\sum_{T|n}\left[\sum_{k|T}\mu(k)k^y\left(\frac{T}{k}\right)^x\right]\left(\frac{n}{T}\right)^i\end{aligned}$$ 注意到最后两层的和式嵌套实际上是三个函数的迪利克雷卷积,令$f(n)=\mu(n)n^y$,则有$$n^y\sum_{i=1}^{y+1}a_i\sum_{T|n}\left[\sum_{k|T}\mu(k)k^y\left(\frac{T}{k}\right)^x\right]\left(\frac{n}{T}\right)^i=n^y\sum_{i=1}^{y+1}a_i(f*\text{id}_x*\text{id}_i)(n)$$ 考虑到$(f*\text{id}_x*\text{id}_i)(n)$是积性函数,所以考虑求出其在质数的若干次幂处的值$$(f*\text{id}_x*\text{id}_i)(p^c)=(\text{id}_x*\text{id}_i)(p^c)-p^y(\text{id}_x*\text{id}_i)(p^{c-1})$$ 而后面的两部分就是一个等比数列求和,暴力算即可(没必要快速幂,都是${\log}$级别的)

然后Pollard-ρ质因数分解,实现不好可能会TLE.