题目描述
对于一个正整数n，定义f(n)为它十进制下每一位数字的平方的和。现在给定三个正整数k,a,b，请求出满足a<=n<=b且k*f(n)=n的n的个数。
输入
第一行包含三个正整数k,a,b(1<=k,a,b<=10^18,a<=b)。
输出
输出一个整数，即满足条件的n的个数。
样例输入
51 5000 10000
样例输出
3
题解
暴力
考虑一个$\le 10^{18}$的正整数，它的$f$值最大只有$f(999999999999999999)=9*9*18=1458$。
所以可以枚举$f(n)$，然后判断是否有满足条件的$n$即可。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll k , a , b;
ll calc(ll n)
{
ll ans = 0;
while(n) ans += (n % 10) * (n % 10) , n /= 10;
return ans;
}
ll solve(ll n)
{
ll i , ans = 0;
for(i = 1 ; i <= 1458 ; i ++ )
{
if(i * k > n) break;
if(calc(i * k) == i) ans ++ ;
}
return ans;
}
int main()
{
scanf("%lld%lld%lld" , &k , &a , &b);
printf("%lld\n" , solve(b) - solve(a - 1));
return 0;
}