版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [Luogu P6156] 简单题" categories:
强烈谴责这种起无意义标题的做法
<!-- more -->zbw 遇上了一道题, 由于他急着去找 qby, 所以他想让你来帮他做
给你 $n,k$ 求下式的值:
$$ \sum\limits{i=1}^n\sum\limits{j=1}^n(i+j)^kf(\gcd(i,j))\gcd(i,j) $$
其中 $\gcd(i,j)$ 表示 $i,j$ 的最大公约数
$f$ 函数定义如下:
如果 $k$ 有平方因子 $f(k)=0$, 否则 $f(k)=1$
就是 $\mu^2$
Update:平方因子定义 如果存在一个整数 $k(k>1),k^2|n$ 则 $k$ 是 $n$ 的一个平方因子
请输出答案对 $998244353$ 取模的值
一行两个整数 $n,k$
一行一个整数, 表示答案对 $998244353$ 取模后的值
3 3
1216
2 6
9714
18 2
260108
143 1
7648044
| 测试点 | $n$ | $k$ |
|---|---|---|
| $1,2$ | $\leq10^3$ | $\leq10^3$ |
| $3,4$ | $\leq2 \times 10^3$ | $\leq10^{18}$ |
| $5 \sim8$ | $\leq5 \times 10^4$ | $\leq10^{18}$ |
| $9$ | $\leq 5\times10^6$ | $=1$ |
| $10,11$ | $\leq 5\times10^6$ | $=2$ |
| $12,13$ | $\leq 5\times10^6$ | $\leq10^3$ |
| $14 \sim20$ | $\leq 5\times10^6$ | $\leq10^{18}$ |
对于 $100\%$ 的数据, $1 \leq n \leq 5 \times 10^6$, $1 \leq k \leq 10^{18}$
Update on 2020/3/16: 时间调至 $1$s,卡掉了 $O(n\log k)$,$O(n\log mod)$ 的做法
推式子
$$ \begin{aligned} \sum{i=1}^n\sum{j=1}^n(i+j)^k\mu^2((i,j))(i,j)&=\sum{d=1}^nd^{k+1}\mu^2(d)\sum{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum{j=1}^{\lfloor\frac{n}{d}\rfloor}(i+j)^k[(i,j)=1]\ &=\sum{d=1}^nd^{k+1}\mu^2(d)\sum{e=1}^{\lfloor\frac{n}{d}\rfloor}e^k\mu(e)\sum{i=1}^{\lfloor\frac{n}{de}\rfloor}\sum{j=1}^{\lfloor\frac{n}{de}\rfloor}(i+j)^k\ &\xlongequal[D=de]{S(x)=\sum{i=1}^x\sum{j=1}^x(i+j)^k}\sum{D=1}^nD^kS\left(\left\lfloor\frac{n}{D}\right\rfloor\right)(\mu*{\operatorname{id}\mu^2})(D) \end{aligned} $$
其中
$O(n)$