Really Big Numbers
题目描述
Ivan likes to learn different things about numbers, but he is especially interested in really big numbers. Ivan thinks that a positive integer number $x$ is really big if the difference between $x$ and the sum of its digits (in decimal representation) is not less than $s$. To prove that these numbers may have different special properties, he wants to know how rare (or not rare) they are - in fact, he needs to calculate the quantity of really big numbers that are not greater than $n$.
Ivan tried to do the calculations himself, but soon realized that it’s too difficult for him. So he asked you to help him in calculations.
题意概述
问区间$[1, n]$中有多少个数$t$满足$t-sum_t \ge s$,其中$sum_t$表示$t$各位数字之和。
数据范围:$1 \le n, s \le 10^{18}$。
算法分析
定义函数$g(x)$表示$x$各位数字之和,$f(x)=x-g(x)$。可以发现$f(x)$在$N^*$上单调不递减。因此直接二分找出满足$f(x) \lt s$的$x$的最大值,再与$n$作差即可。
下面来证明$f(x)$在$N^*$上单调不递减。
将$x$表示成
$$
\overline{a_1a_2a_3 \ldots a_{t-1}a_t}
$$研究$g(x)$的增减性。如果$a_t \lt 9$,那么$g(x+1)=g(x)+1$;否则,可以将$x+1$表示成
$$
\overline{a_1a_2a_3 \ldots (a_{t-1}+1)0}
$$$g(x+1)=g(x)-8$。如果$a_{t-1}=9$,那么就再向前进位使$g(x+1)=g(x)-17$…易知$g(x+1) \le g(x)+1$。所以
$$
\begin{align}
f(x+1)-f(x)&=(x+1)-g(x+1)-(x-g(x)) \\
&=g(x)+1-g(x+1) \ge 0
\end{align}
$$
由此得证。
代码
1 |
|