# 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.

## 算法分析

$$\overline{a_1a_2a_3 \ldots a_{t-1}a_t}$$

$$\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;
}

418 I'm a teapot