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
#include <iostream>
#include <algorithm>

using namespace std;

long long inline sqr(long long n)
{
    return n*n;
}

long long inline f(long long n) {
    long long result = 0;
    while (n) {
        result += sqr(n % 10);
        n /= 10;
    }
    return result;
}

long long program(long long k, long long a, long long b) {
    long long max_b = 0, b_copy = b;
    while (b_copy) {
        max_b += 81;
        b_copy /= 10;
    }
    long long counter = 0;
    b = min(b, k*max_b); /// B = min(b, k log b)
    a = ((a + k - 1) / k) * k;
    for (long long n = a; n <= b; n += k) /// O((B log n)/k) = O(min(b/k, log b) log n)
        if (k * f(n) == n)
            ++counter;
    return counter;
}

int main() {
    ios_base::sync_with_stdio(0);
    long long k, b, e;
    cin >> k >> b >> e;
    cout << program(k, b, e);
    return 0;
}