## 题目描述

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}

$$

由此得证。

## 代码

#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; }