hexo-blog/source/_posts/oi/really-big-numbers.md

---

title: Really Big Numbers tags:

• Binary-Search id: "519" categories:
• - OI
  • Common Skill date: 2017-06-19 19:00:15 ---

题目描述

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_2a3 \ldots a{t-1}a_t} $$

研究$g(x)$的增减性。如果$a_t \lt 9$，那么$g(x+1)=g(x)+1$；否则，可以将$x+1$表示成

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