自动搬运

查看原文

来自洛谷，原作者为

	CSP_Sept 私が戻ってきたのはね。 もう一度、星の音を聞くためだよ

搬运于2025-08-24 22:38:50，当前版本为作者最后更新于2022-06-22 14:53:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Official Editorial.

题意

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

解法

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. $1\le l\le r\le\varphi(k-1)$
   直接暴力处理 $f(i^i)$ 的前缀和并将其存入 map，枚举计算即可。时间复杂度为 $O(k \log k)$。
2. $1\le l\le\varphi(k-1)<r$
   将其分为两部分处理。
   • $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. $\varphi(k-1)<l\le r$
   考虑钦定 $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 或洛谷氪金即可获得。