hiho-[Offer收割]编程练习赛65-题目4 : 解方程

题目链接:https://hihocoder.com/problemset/problem/1771

题意

设 f(n) 表示 n 的每一位数字的平方之和，求 [a,b] 中有几个 n 满足 k × f(n)=n (1 ≤ k, a, b ≤ 10¹⁸，且a ≤ b)

解法

由于f(n)表示每一位数字的平方之和，那么f(n)的范围最大不超过18*9*9，那么只需要枚举f(n)，反推出来n并判断即可。

#include <iostream>
using namespace std;
using ll = long long;

ll calc(ll x) {
    ll res = 0;
    while(x) {
        res += (x%10) * (x%10);
        x /= 10;
    }
    return res;
}

int main() {
    ll k, a, b;
    cin>>k>>a>>b;
    ll res = 0;
    for(int i=1; i<=18*9*8; i++) {
        ll n = k * i;
        if(n >= a && n <= b && calc(n)*k == n) res ++;
    }
    cout<<res<<endl;
    return 0;
}