2014 吉林省赛题解 | CCUT应用OJ题解——F[X] + X = N

题目简介

• 题意：对于任意十进制整数 \(X\)，定义 \(F[X]^\dagger\) 表示其循环左移一位所得到的数。给定非负整数 \(N\)，求所有满足等式 \(X+F[X]=N\) 的 \(X\) 的个数。
  \(\dagger\) 循环左移：设 \(X=a_0a_1\cdots a_m\)，则 \(F[X]=a_1\cdots a_ma_0\)。若 \(X\) 为一位整数，则 \(F[X]=X\)；若 \(F[X]\) 包含前导零则忽略。
• 数据范围：\(0\le N\le 10^{18}\)

题解

设 \(X\) 是一个 \(L\) 位数，分别将 \(X\) 与 \(F[X]\) 进行位权展开：\(X = a_0 \times 10^{L-1} + a_1 \times 10^{L-2} + \cdots + a_{L-2} \times 10 + a_{L-1}；F[X] = a_1 \times 10^{L-1} + a_2 \times 10^{L-2} + \cdots + a_{L-1} \times 10 + a_0\)。

记 \(X = a \times 10^{L-1} + b\)，其中 \(a\) 为首位数字\(1–9\)，\(b\) 为剩余 \(L-1\) 位，则 \(F[X] = b \times 10 + a\)，代入题中得：\(X+F[X]=a(10^{L-1} + 1) + 11b=N\)，移项得 \(b = \frac{N - a(10^{L-1} + 1)}{11}\)。

只要满足 \(b\) 为整数，\(0 \le b < 10^{L-1}\)，就说明存在这样的 X。

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main(){ios::sync_with_stdio(0),cin.tie(0);int T;while (cin >> T) {while(T--){long long N; cin >> N;long long ans = 0;for(int L=1; L<=19; ++L){long long poww = powl(10,L-1);int st = L==1? 0 : 1;for(int a=st; a<=9; a++){long long rem = N - a * (poww + 1);long long r = rem / 11;if (!(rem % 11)&&r >= 0 && r < poww) ans++;}}cout << ans << '\n';}}return 0;
}