自动搬运

查看原文

来自洛谷，原作者为

	Fiendish i AM a LAD,ANd Fine.

搬运于2025-08-24 23:15:14，当前版本为作者最后更新于2025-05-02 19:21:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

函数 $f_k(x)$ 是一个十分有趣的函数。

可以先做一下变形。

$\begin{aligned}f_k(x)=S_0(x)+S_1(x)+S_2(x)\dots&=x+s(x)+S_0(s(x))+S_1(s(x))+\dots\\&=f_{k-1}(s(x))+x\end{aligned}$

若 $f_k(x)=m$，则 $m-f_{k-1}(s(x))=x$。

由此可以看出符合条件的 $x$ 不会超过 $m$。

因此，问题转化为每次询问有多少个 $s(x)$ 使得 $s(m-f_{k-1}(s(x)))=s(x)$。由于 $x\le m$，所以 $s(x)$ 不会很大，最大就到 $162$（当 $x=10^{18}-1$ 时）。因此我们可以先预处理出 $f_{k-1}(i),i\in[1,162]\land i\in\mathbb Z$，处理询问时枚举所有可能的 $s(x)$ 并对答案进行统计。时间复杂度 $O(T\log m)$。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long s(long long x){//求一个数在十进制下的各位数字之和
	long long ans=0;
	while(x) ans+=x%10,x/=10;
	return ans;
}
long long S[200][5];
long long f[200];//由于 k 是固定的，所以只需要开一维
int T,k;
long long m;
int main(){
	cin>>T>>k;
	for(int i=1;i<=162;i++){//预处理
		S[i][0]=i;
		S[i][1]=s(S[i][0]);
		S[i][2]=s(S[i][1]);
		if(k<=3)
			for(int j=0;j<k;j++) f[i]+=S[i][j];
		else f[i]=S[i][0]+S[i][1]+S[i][2]+1ll*(k-3)*S[i][2];
	}
	while(T--){
		cin>>m;
		long long ans=0;
		for(int i=1;i<=162;i++)//枚举 s(x)
			if(s(m-f[i])==i) ans++;
		cout<<ans<<'\n';
	}
}