Dream__Sky @ 2023-09-03 13:46:48
给定数字 K 和 N，构造一个长度为 N 的排列，每个元素的大小为 [1,K] (可重复)，
计算所有这些可能的排列的 GCD 之和，输出所有和 \mod 10^9+7 后的结果。
1\leq K\le 10^5
2\leq N\le 10^5
by Hozuki_Kaede @ 2023-09-03 15:59:28
@Dream__Sky 首先这不叫排列，一般叫序列/数列。
题意即求 \displaystyle S=\sum_{a_1=1}^K\cdots\sum_{a_N=1}^K\gcd(a_1,\dots,a_N).
枚举 gcd 用 Mobius 反演，
S&=\sum_{d=1}^K\sum_{a_1=1}^{\lfloor\frac Kd\rfloor}\cdots\sum_{a_N=1}^{\lfloor\frac Kd\rfloor}d[\gcd(a_1,\dots,a_n)=1]\\
&=\sum_{d=1}^Kd\sum_{a_1=1}^{\lfloor\frac Kd\rfloor}\cdots\sum_{a_1=1}^{\lfloor\frac Kd\rfloor}\sum_{q\mid\gcd(a_1,\dots,a_n)}\mu(q)\\
&=\sum_{d=1}^Kd\sum_{q=1}^{\lfloor\frac Kd\rfloor}\mu(q)\left\lfloor\dfrac K{dq}\right\rfloor^N\\
&=\sum_{Q=1}^Kf(Q)\left\lfloor\dfrac K{Q}\right\rfloor^N,
\end{aligned}
其中 f(Q=dq) 为 Id(d)=d 与 \mu(q) 的狄利克雷卷积。求 f 的前缀和，再整除分块就可以解决多组数据。