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
#include "stdio.h"

static int const p2[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 };
static int const max_n_k = 1458;

int f(long long n) {
    int r = 0;
    do {
        int nextDigit = n % 10;
        r += p2[nextDigit];
        n /= 10;
    } while (n > 0);
    return r;
}

int main() {
    long long k, a, b;
    scanf("%lld %lld %lld", &k, &a, &b);
    int result = 0;
    long long n_k = a / k + ((a % k > 0) ? 1 : 0);
    long long n = n_k * k;
    while ((n <= b) && (n_k <= max_n_k)) {
        if (f(n) == n_k) {
            ++result;
        }
        ++n_k;
        n += k;
    }
    printf("%d\n", result);
    return 0;
}