题意
- 来源：1134 - 重复数 | CCUTOJ
- 题意：在等式 \(A+B=C\) 中，若 \(C>10\) 且 \(C\) 中各数位相同，则定义 \(A,B\) 为重复数，其中\(A\le B\)。求 \([X,Y]\) 中存在几对重复数。
- 数据范围：\(1\le X\le Y\le 10^6\)
题解
由于 \(A,B\le 10^6\)，故 \(C\le 2\times 10^6\)。
手写出几个可能的 \(C\) ：\(C=11,22,\dots,99,111,222,\dots,999,\dots\)，可发现 \(C\) 中每多一个位数，\(C\) 的数量 \(+9\)。因此当 \(C\) 上界为 \(2\times 10^6\) 时，\(C\) 的数量不会超过 \(100\)。因此我们预处理出所有的 \(C\)，并反推出所有 \((A,B)\)。
我们将固定 \(A\)，将所有的 \(B\) 均替换为 \(A\) 的形式，则\(B=C-A\)。\(A\) 的约束条件包括：
\[\begin{align}
X\le A,B\le Y\\
A\le B
\end{align}\]
将 \((1)\) 式改写为 \(X\le A\le Y, X\le C-A\le Y\)，故：
\[\begin{equation}
C-Y\le A\le C-X
\end{equation}\]
将 \((2)\) 式改写为：
\[\begin{equation}
A\le \frac{C}{2}
\end{equation}\]
整理可得：
\[\begin{cases}
X & \le A \le \frac{C}{2}\\
C-Y & \le A \le C-X
\end{cases}\]
我们只需对上述不等式取交集，即可确定 \(A\) 的取值范围：
\[\max(X,C-Y)\le A\le \min(\frac{C}{2},C-X)
\]
这一范围内每个元素均为A。记 \(low=\max(X,C-Y), high=\min(\frac{C}{2},C-X)\)：
- 若 \(high<low\)，无解
- 否则，答案即为 \(high-low+1\)。
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
const i64 MAX = 2000000;
vector<i64> c;
void init() {for (int k = 2; k <= 9; k++) {for (int d = 1; d <= 9; d++) {i64 temp = 1LL * (int)((pow(10, k) - 1) / 9) * d;if (temp > MAX) break;c.push_back(temp);}}sort(c.begin(), c.end());
}
int main() {ios::sync_with_stdio(0),cin.tie(0);init();i64 x, y;while (cin >> x >> y) {i64 ans = 0;for (auto i : c) {i64 low = max(x, i - y);i64 high = min(y, min(1LL * i / 2, i - x));if (high >= low) {ans += (high - low + 1);}}cout << ans << "\n";}return 0;
}