P12397 「FAOI-R9」函数大师 题解

Statement

• $s(x)$ 为 $x$ 在十进制下各个数位上的数之和，即 $s(x)=\sum\limits_{i=0}^\infty\left(\left\lfloor \dfrac{x}{10^i} \right\rfloor \mathrm{mod}\;10\right)$。
• $S_k(x)=\begin{cases} x & k=0 \\ s(S_{k-1}(x)) & k \ge 1 \end{cases}$。
• $f_k(x)=\sum\limits_{i=0}^k S_i(x)$。

Analysis

• 当 $k=0$ 时：
  • 由题意知 $f_0(x)=x=m$。
  • 答案显然为 $1$。
• 当 $k=1$ 时：
  • 由题意知 $f_1(x)=x+s(x)=m$。
  • 由于 $x$ 可能很大，枚举 $x$ 无法接受，故考虑枚举较小的 $s(x)$。
  • 具体地，枚举 $a \in [1,162]$，则 $x=m-a$。
  • 验证 $s(x)=a$ 是否成立即可。
• 当 $k=2$ 时：
  • 由题意知 $f_2(x)=x+s(x)+s(s(x))=m$。
  • 类似地，枚举 $a \in [1,162]$，记 $b=s(a)$，则 $x=m-a-b$。
  • 验证 $s(x)=a$ 且 $s(s(x))=b$ 是否成立即可。
• 当 $k \ge 3$ 时：
  • 由题意知 $f_k(x)=x+s(x)+s(s(x))+\dots+S_k(x)=m$。
  • 注意到，当 $k$ 逐渐增大时，$S_k(x)$ 减小极快。
  • 实际上，对于任意 $x \le m \le 10^{18}$，当 $k \ge 3$ 时，$S_k(x)$ 都是相同的。
  • 因此，枚举 $a \in [1,162]$，记 $b=s(a)$，$c=s(b)$，则 $x=m-a-b-(k-2) \times c$。
  • 验证 $s(x)=a$，$s(s(x))=b$ 且 $s(s(s(x)))=c$ 是否成立即可。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
int t, k;
int s(int x){
	int ret = 0;
	while (x > 0){
		ret += x % 10;
		x /= 10;
	}
	return ret;
}
void solve(){
	int m;
	cin >> m;
	int cnt = 0;
	if (k == 0){ //不要忘记 k=0 的情况
		cout << 1 << endl;
		return;
	}
	for (int a = 0;a <= 200;a++){
		int b = s(a), c = s(b), d = s(c);
		if (k == 1){
			int x = m - a;
			cnt += (s(x) == a);
		}
		else if (k == 2){
			int x = m - a - b;
			cnt += (s(x) == a && s(s(x)) == b);
		}
		else{
			int x = m - a - b - c * (k - 2);
			cnt += (s(x) == a && s(s(x)) == b && s(s(s(x))) == c);
		}
	}
	cout << cnt << endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t >> k;
	while (t--) solve();
	return 0;
}