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$作差即可。

$$\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$。所以
f(x+1)-f(x)&=(x+1)-g(x+1)-(x-g(x)) \\
&=g(x)+1-g(x+1) \ge 0



#include <iostream>
using namespace std;
long long n, s, l, r;
bool check(long long t) {
    long long p = t, sum = 0;
    while (p) {
        sum += p % 10;
        p /= 10;
    if (t - sum < s) return false;
    return true;
int main()
    cin >> n >> s;
    l = 0, r = n + 1;
    while (l + 1 < r) {
        long long mid = l + r >> 1;
        if (!check(mid)) l = mid;
        else r = mid;
    cout << n - l << endl;
    return 0;

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *