抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

题目描述

给定一个数 $n$,求在 $[1,n]$ 中 $g(x)=\dfrac{x}{f(f(x))}$ 的取值个数,其中 $f(f(x))$ 表示 $x$ 去掉后面的所有 $0$ 的值。(等价于题目中的:$f(x)$ 为将数反转后去掉前导 $0$)

题目分析

考虑之前的描述,我们只需要考虑 $x$ 后面的 $0$ 的数量就是此题的结果了。理由如下:

给出 $x$,若 $x$ 不含后导 $0$,$g(x)=1$;若有 $1$ 个后导 $0$,$g(x)=10$。不妨设 $x$ 后导 $0$ 的个数为 $k$,则可以得到 $f(f(x))=x\times 10^{-k}$,于是 $g(x)=k$。而 $x$ 的后导 $0$ 数量的取值范围为 $A={x\in\mathbb{N^*}\mid 0 \leq x< \operatorname{length}(x)}$,因此最后 $g(x)$ 在 $[1,n]$ 内可取 $|A|=\operatorname{length}(x)$ 个。

时间复杂度:$\mathcal O(t)$。

发言区

留下自己的足迹吧~