自动搬运

查看原文

来自洛谷，原作者为

	Wind_Smiled 风颜悦。颜悦因风起，风起故颜悦。||向着不同的方向、我们逐渐远去、背对背的你我、难能再见||这个OP的 uid：266896259

搬运于2025-08-24 22:16:17，当前版本为作者最后更新于2022-09-14 15:22:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

对于一个正整数 $n$，定义 $\operatorname{f}(n)$ 为它每一位数字的平方的和。

现在给定三个正整数 $k,a,b$，请求出满足 $a\le n\le b$ 且 $k\times \operatorname{f}(n)=n$ 的 $n$ 的个数。

对于 $100\%$ 的数据，$1\le k,a,b\le 10^{18}$，$a\le b$。

思路

1. 模拟函数 $\operatorname{f}(n)$ 对一个数的操作过程。
2. 重复枚举可能的值，累加答案。

方案一：纯暴力枚举

令 $n$ 的值从 $a$ 到 $b$ 进行枚举，累加可能值的个数。

但是根据数据范围：$1\le k,a,b\le 10^{18}$，$a\le b$，所以 TLE 是不可避免的。

方案二：优化

由题意得：$\operatorname{f}(n)$ 中，$n$ 的取值范围在 $a$ 和 $b$ 之间，令 $a$ 取最小值，$b$ 取最大值时， $n$ 的值最大，极限取值为：$10^{18}-1=99999999999999999$，此时的 $\operatorname{f}(n)$ 的值为 $9^2\times18=1458$。

为方便计算，得出公式：

由题意 $k\times \operatorname{f}(n)=n$

因为两数相等，则每一位相等。

所以 $\operatorname{f}(k\times \operatorname{f}(n))=\operatorname{f}(n)$。

由 $1$ 到 $1458$ 模拟 $\operatorname{f}(n)$ 即可，循环条件为 $\operatorname{f}(n) \times k \le b$。

但是，最后个数会多计算 $\operatorname{f}(n)<a$ 时的一些数，所以，令满足 $\operatorname{f}(n) \le a-1$ 时 $ans$ 逐个减一。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long k,a,b,sum,ans;
long long f(long long x){
    long long ans=0;
    while(x!=0){
        ans+=(x%10)*(x%10);
        x/=10;
    }
    return ans;
}
int main(){
    cin>>k>>a>>b;
    for(int i=1;i<=1458&&i*k<=b;i++){
        if(f(i*k)==i){
            ans++;
        }
    }
    for(int i=1;i<=1458&&i*k<=a-1;i++){
        if(f(i*k)==i){
            ans--;
        }
    }
    cout<<ans;
    return 0;
}