自动搬运

查看原文

来自洛谷，原作者为

	ydzr00000 So you...

搬运于2025-08-24 22:52:49，当前版本为作者最后更新于2023-11-27 07:46:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面

令 $f(x)$ 表示 $x$ 中各个数位上的数字的封闭部分的数量，再令 $g^0(x)=x$，对于 $k\ge 1$ 满足 $g^k(x)=f(g^{k-1}(x))$，给定 $T$ 组 $x,k$，试求 $g^k(x)$。

$T\leq 10^5, x,k\leq 10^9$。

题解

首先让我们考虑 $g^1(x)$ 的值，因为 $8$ 的封闭部分最多（有 $2$ 个），所以 $g^1(x)$ 在 $x=888,888,888$ 时取到最大值，为 $18$。

再考虑 $g^2(x)$ 的值，因为 $0\leq g^1(x)\leq 18$，计算所有可能的 $g^2(x)$，可以发现 $0\leq g^2(x)\leq 2$。

再类推一次，可以得到 $0\leq g^3(x)\leq 1$。

在 $k\ge 3$ 的时候，$g^k(x)$ 不等于 $0$ 就会等于 $1$，事实上，可以发现之后的部分为 $0,1$ 交替的循环，因为 $f(0)=1,f(1)=0$。

于是最多循环 $3$ 次，若 $k\ge 3$ 的时候判断最后的值是 $0$ 还是 $1$ 即可。

我们可以认为暴力计算 $f(x)$ 的时间复杂度是 $\log_{10}x$，于是最终时间复杂度为 $\mathcal{O}(T\log_{10}x)$。

注意一下 $f(0)=1$，一些写法可能使得 $f(0)=0$。