P5991 [PA2015]Równanie

Wind_Smiled · 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;
}