1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <math.h>

using namespace std;

int calculate(unsigned long long k, unsigned long long a, unsigned long long b);

int main()
{
    unsigned long long k;
    unsigned long long a;
    unsigned long long b;
    scanf("%lld %lld %lld", &k, &a, &b);
    cout << calculate(k, a, b) << endl;
    return 0;
}

unsigned long long getSumOfSquares(unsigned long long n) {
    unsigned long long result = 0;
    while (n != 0) {
        unsigned long long m = n % 10;
        result += m * m;
        n /= 10;
    }

    return result;
}

int calculate(unsigned long long k, unsigned long long a, unsigned long long b)
{
    int result = 0;
    unsigned long long n_min = ((unsigned long long)(a / k)) * k;
    if (n_min < a) {
        n_min += k;
    }

    unsigned long long n_max = k * 81 * ((unsigned long long)log((double)b) + 1);
    n_max = min(n_max, b);

    for (unsigned long long n = n_min; n <= n_max; n += k) {
        if (getSumOfSquares(n) * k == n) {
            result++;
        }
    }

    return result;
}