The Solution of P8412

· · 题解

Official Editorial.

题意

定义函数 f_k(x)，给定 k,p，构造 l,r 使得

\sum\limits_{i=l}^rf_k(i^i)=p

解法

Subtask 1

直接输出 \texttt{-1} 即可。

Subtask 2

直接暴力枚举并用 map 维护即可。时间复杂度为 O(T N \log N)。

Subtask 3

首先，我们需要知道 f 函数满足 f(A) = (A - 1) \bmod (k - 1) + 1。

证明：令 A 在 k 进制下各位分别为 a_0, a_1, \cdots, a_m，f'(x) = \displaystyle\sum_{i = 0}^m a_i，则 f'(A) 表示 A 在 k 进制下每一位的和，且 d(A) 即为不断地令 A \leftarrow f'(A) 直到 A < k。

因为 k^i \equiv 1 \pmod{k - 1}，所以 A = \displaystyle\sum_{i = 0}^m k^i a_i \equiv f'(A) \pmod{k - 1}。证毕。

注意到 f(A) 在这里不能为 0，于是当 k - 1 \mid A，令 f(A) = k 即可。

接下来根据构造出的 l, r 分类讨论。

  1. 直接暴力处理 $f(i^i)$ 的前缀和并将其存入 map，枚举计算即可。时间复杂度为 $O(k \log k)$。
  2. 将其分为两部分处理。 - $l\le i\le\varphi(k-1)$：同上。 - $\varphi(k-1)<r$：考虑扩展欧拉定理，发现此时 $f(i^i)$ 存在循环节，循环节起点为 $\varphi(k-1) + 1$，循环节长度为 $\operatorname{lcm}(k-1,\varphi(k-1))$。考虑预处理出**整个循环节中前缀和 $\leq p$ 的部分**并枚举循环次数以及在 map 中查询。时间复杂度为 $O(\log k(k^2 + \frac{p}{k}))$。
  3. 考虑钦定 $l$ 位于第一个循环节中（反正都要循环）。\ 接下来先特判 $l,r$ 均位于第一个循环节的情况，然后再枚举 $r$ 位于第几个循环节。设一个循环节内 $f(i^i)$ 的和为 $sum$，考虑到 $l \sim r$ 之间（不包括 $l,r$ 所在循环节）的循环节数 $cnt$ 一定满足 $cnt\cdot sum\le p\le sum\cdot(cnt+2)$，直接枚举至多三个循环节即可。时间复杂度为 $O(k^2 \log k)$。

综上，时间复杂度为 O(T \log k(k^2 + \frac pk))。

Subtask 4

加上哈希即可。

时间复杂度为 O(T(k^2 \log k + \frac pk))。

代码

向 CSP_Sept 或洛谷氪金即可获得。