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
// Karol Kosinski
#include <cstdio>
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;

typedef unsigned long long LG;
const LG MXS = 18 * 9 * 9;
const LG BIG_K = 1234567890123456ull;

LG new_a(LG a, LG k) {
        return (a + k - 1) / k * k;
}

LG new_b(LG b, LG k) {
        if( k > BIG_K ) return b;
        LG fmax = k * MXS;
        return (fmax < b) ? fmax : b;
}

LG f(LG n) {
        LG sum = 0;
        while(n > 0) {
                int j = n % 10;
                sum += j * j;
                n /= 10;
        }
        return sum;
}

int main() {
        LG k, a, b;
        int counter = 0;
        scanf("%llu%llu%llu", &k, &a, &b);
        a = new_a(a, k);
        b = new_b(b, k);
        DEBUG("From %llu to %llu step %llu:\n", a, b, k);
        for(LG i=a; i<=b; i+=k)
                if(k * f(i) == i) {
                        DEBUG("* %llu\n", i);
                        ++counter;
                }
        printf("%d\n", counter);
        return 0;
}