题面#

Let’s define $F(x)$ as the sum of the digits of $x$. An integer $x$ is considered beautiful if $F(F(x)) = F(x)$.

You are given an integer $x$. In one move, you can choose any digit in the number and replace it with another. The resulting number cannot have leading zeros.

Your task is to calculate the minimum number of moves (possibly zero) required to make the given number beautiful.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The only line of each test case contains a single integer $x$ ($1 \le x \le 10^{18}$).

Output

For each test case, print a single integer — the minimum number of moves (possibly zero) required to make the given number beautiful.

思路#

先分析题意：

设 $y$ 的十进制位数为 $k$，

若 $k\ge 2$，则 $y \ge 10^{k-1}$，数位和最多是 $9k$，

因此有 $F(y) \le 9k < 10^{k-1} \le y$，从而当 $y\ge 10$ 时一定有 $F(y) < y$

这说明方程 $F(y)=y$ 只能在 $y$ 为一位数时成立，也就是 $y \in [0,9]$

因此 $F(F(x)) = F(x)$ 等价于 $F(x)$ 本身是一位数，即 $F(x) \le 9$ 于是题目变成把 x 的数位和变到不超过 9，并且操作次数最少

那么，

设原数位和 $S = F(x)$ 若 $S \le 9$，$x$ 已经漂亮，答案为 0 若 $S > 9$，至少需要把数位和减少 $need = S - 9$

代码#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
long long F(long long x) {
6
    auto s = to_string(x);
7
    long long result = 0;
8
    for (auto c : s) {
9
        result += c - '0';
10
    }
11
    return result;
12
}
13

14
int main() {
15
    int t;
16
    cin >> t;
17
    while (t --) {
18
        long long x;
19
        cin >> x;
20

21
        long long sum = F(x);
22
        if (sum <= 9) {
23
            cout << 0 << '\n';
24
            continue;
25
        }
26

27
        int need = static_cast<int>(sum - 9);
28

29
        string s = to_string(x);
30
        vector<int> caps;
31
        caps.reserve(s.size());
32

33
        for (int i = 0; i < (int)s.size(); i ++) {
34
            int d = s[i] - '0';
35
            caps.push_back(i == 0 ? d - 1 : d);
36
        }
37

38
        sort(caps.rbegin(), caps.rend());
39

40
        int ans = 0;
41
        for (int cap : caps) {
42
            if (need <= 0) break;
43
            need -= cap;
44
            ans ++;
45
        }
46

47
        cout << ans << '\n';
48
    }
49
}