给定两个正整数 \(x, y\) 。变量 \(k\) 一开始为 \(0\) 。你可以多次进行以下两种操作之一：
- 对 \(k\) 加 \(1\) 。
- 对 \(k\) 加 \(x \cdot 10^p\) ，\(p\) 可以是任意一个非负数。
需要找到最小的操作次数使 \(k\) 到 \(y\) 。
及其显然地，操作二中 \(x \cdot 10^{p_1}\) 可以被若干个 \(x \cdot 10^{p_2}\) 表示，当且仅当 \(p_1 > p_2\) 。显然 \(x \cdot 10^{p}\) 可以被 \(1\) 表示。于是可以按贡献尽可能大的操作二贪心，再按操作一贪心。
问题在于如何找到最大的 \(p\) 。可知 \(k + x \cdot 10^p \leq y\) 。于是 \(10^p \leq \frac{y - k}{x}\) 。
由于值域原因，预处理出 \(\lfloor \log_{10} x \rfloor\) 是时间不合法的。但由于 \(p\) 会逐渐减小，所以可以贪心地将 \(p\) 从大到小枚举，取上限 \(1 \cdot 10^{9}\) ，即 \(p_{max} = 9\) 。贪心地迭代到 \(y - k < x\) ，再加上 \(y - k\) 即最小操作数。
时间复杂度为 \(O(\log n)\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve() {
int x, y; std::cin >> x >> y;
int k = 0, cnt = 0;
for (int p = 9; ~p; --p) {
while (1LL * k + 1LL * x * (ll)pow(10, p) <= y) {
k += 1LL * x * (ll)pow(10, p);
cnt += 1;
}
}
cnt += y - k;
std::cout << cnt << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while(_--) { solve(); }
return 0;
}