题解：P1660 数位平方和

Problem Link

Step 1：

“定义 \(S(n)\) 表示 \(n\) 个的各个数位的 \(k\) 次方的和。”

数位的 \(k\) 次方，我们可以通过快速幂求出，为了节省时间，我们可以定义一个 \(a\) 数组，来表示 \(0\sim9\) 区间中各数字 \(k\) 次方的值。

然后我们通过定义一个 \(s\) 数组来存储 \(0\sim4\times10^{6}\) 区间中各数字的 \(S\) 值。

Step 2：

“定义 \(H(n)\) 为满足 \(H(n) \le \min\{n, H(S(n))\}\) 的最大值。“

关于这个，不难想到通过递归求出 \(H(n)\) 的值。

但是，进行手动模拟后不难发现，有些时候直接将 \(H(i)=\min{n,H(S(i))}\) 会造成死循环。

例子：当 \(k=2\)，\(n=2\) 时，求 $ H(2)$ 即求 $ H(4) \Rightarrow H(16) \Rightarrow H(37) \Rightarrow H(58) \Rightarrow H(89) \Rightarrow H(145) \Rightarrow H(42) \Rightarrow H(20) \Rightarrow H(4) \Rightarrow H(16) \dots $　

显然，这形成了一个环，此时不难想到“环上最小值就是整个环相同 \(H\)。”

所以我们可以通过定义一个 \(mark\) 数组来表示个点的访问次数，若 mark[i]==2 则说明出现了环，那你就再走一次去寻找并更新环上最小值。

这时不难想到通过定义一个 \(h\) 数组来实现记忆化搜索，又省了一些时间。

Step 3：

此时你会发现题目已经做完，剩下仅需处理一些细节同时略微整合一下代码便可以 \(\color{black}\texttt{AC}\) 了。

//written by naught
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<climits>
using namespace std;

typedef long long ll;
#define Maxn 4000005 //4倍空间
#define Mod 10000007

inline ll read(ll x=0,bool f=0,char c=getchar()){while(!isdigit(c))f=c=='-',c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();return f?-x:x;}

ll k,A,B,m;
ll ans;
ll a[12],s[Maxn],h[Maxn],mark[Maxn];

ll hts(ll x,ll y) //快速幂
{
    m=1;
    while(y)
    {
        if(y%2==1)
        {
            m*=x;
            m%=Mod;
        }
        x*=x;
        x%=Mod;
        y/=2;
    }
    return m;
}

ll S(ll x) //求S
{
    m=0;
    while(x)
    {
        m+=a[x%10];
        m%=Mod;
        x/=10;
    }
    return m;
}

ll H(ll x) //求H
{
    if(h[x]) return h[x]; //记忆化搜索
    if(mark[x]==2) return x;
    ++mark[x];
    h[x]=min(x,min(s[x],H(s[x]))); //处理环
    --mark[x];
    return h[x];
}

int main()
{
    k=read(),A=read(),B=read();
    for(ll i=0;i<10;++i){
        a[i]=hts(i,k);
    }
    for(ll i=0;i<Maxn;++i){
        s[i]=S(i);
    }
    h[0]=0;
    h[1]=1;
    for(ll i=A;i<=B;++i){
        ans+=H(i);
        ans%=Mod; //勿忘取模
    }
    printf("%lld",ans);
    return 0;
}