P5991题解

_xiaxii · 2022-08-14 22:25:56 · 题解

题意传送门

题意分析：

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

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

思路1

从 a 到 b 暴力枚举 n，这样显然会时间超限：

#include <bits/stdc++.h>
using namespace std;

long long k,a,b;
int cnt;

long f(int x)
{
    long sum=0;
    while(x!=0)
    {
        sum+=(x%10)*(x%10);
        x/=10;
    }
    return sum;
}

int main()
{

    cin>>k>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(i%k==0)//缩短时间（但是看起来没什么必要了
        {
            if(f(i)*k==i)
            {
                cnt++;
            }
        }
    }
    cout<<cnt;
    return 0;
}

预计得分:18(TLE)。

思路二

从数据范围中我们可以知道 1\le k,a,b\le 10^{18}，因为 n\le b ，所以 n 最大值为 1000000000000000000，但是考虑到是每一位的平方之和，所以 \operatorname{f}(n) 最大值为 \operatorname{f}(999999999999999999)=9^{2}\times 18=1458。

我们知道了数据范围，将推导的公式代入代码，这能大大节约我们的时间：

#include <bits/stdc++.h>
#define ll long long//将所有数据类型换成long long

using namespace std;

ll k,a,b;//定义全局变量是个好习惯
int cnt;//使用cnt对答案计数

ll f(ll x)//定义f(ll x)函数对数进行拆分
{
    ll sum=0;
    while(x!=0)
    {
        sum+=(x%10)*(x%10);
        x/=10;
    }
    return sum;
}

int main()
{

    cin>>k>>a>>b;//读入数据
    for(int i=1;i<=1458&&i*k<=b&&i*k>=a;i++)
    {
        if(f(i*k)==i)//调用函数判断是否成立
        {
            cnt++;//对成立的个数进行计数
        }
    }

    cout<<cnt;//输出cnt
    return 0;//圆满结束~~
}

预计得分:100。

本蒟蒻的第一篇题解。