博客

思路:对[l,r]区间的数进行两次遍历，第一次遍历对每个数找依附于它的幸福数，将这些数标记，第二次遍历找所有未被标记的数，判断其是否是幸福数，并找出依附于它的数的个数作为其独立性，若该数为素数，独立性翻倍，这个过程我通过dfs来完成

代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const ll maxn=1e4+9;
ll flag=0,cnt=0,ans,tar;
ll vis[maxn],mp[maxn],prime[maxn],book[maxn];
set<ll>st;
ll l,r;
void solve(ll v){
    ll sum=0,u=v;
    if(v==1){
        flag=1;
        return;
    }
    while(u){
        sum+=(u%10)*(u%10);
        u/=10;
    }
    if(vis[sum])return;
    vis[sum]=1;
    solve(sum);
    vis[sum]=0;
    if(flag){
        if(v!=tar&&v<=r&&v>=l)
        st.insert(v);
    }
    return;
}
void to_pr(){
    for(ll i=2;i<=maxn;i++){
        if(!book[i])prime[i]=1;
        for(ll j=i*i;j<=maxn;j+=i){
            book[j]=1;
        }
    }
}
void to_answer(ll v){
    ll sum=0,u=v;
    if(v==1){
        flag=1;
        ans=cnt;
        return;
    }
    while(u){
        sum+=(u%10)*(u%10);
        u/=10;
    }
    if(vis[sum])return;
    vis[sum]=1;
    cnt++;
    to_answer(sum);
    cnt--;
    vis[sum]=0;
    return ;
}
int main(){
    to_pr();
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,n;
    cin>>l>>r;
    for(ll i=l;i<=r;i++){
        flag=0;tar=i;
        solve(i);
    }
    for(auto it:st){
        mp[it]=1;
    }
    int ff=0;
    for(i=l;i<=r;i++){
        flag=0;
        if(!mp[i]){
            to_answer(i);
            if(flag){ff=1;
                if(prime[i])ans*=2;
                cout<<i<<' '<<ans<<endl;
            }
        }
    }
    if(!ff)cout<<"SAD"<<endl;
}