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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <string>
#define LL long long

using namespace std;

int  f (LL n) {
    int out = 0;
    while (n) {
	out += (n % 10) * (n % 10);
	n /= 10;
    }
    return out;
}
int check (LL number, LL k) {
    if (number % k)
	return 0;
    return (number / k) == f (number) ? 1 : 0;
}

LL min (LL a, LL b) {
    return a > b ? b : a;
}

void sharp_bound (LL k, LL *b) {
    LL tmp = 685871056241426l;
    if (k > tmp)
	return;
    LL bound = k * 1458;
    *b = min (*b, bound);
}

LL closest_multiplicity (string type, LL number, LL divisor) {
    LL residue = number % divisor;
    if (type == "upper") {
	if (residue)
	    return number + divisor - residue;
	else
	    return number;
    }
    if (type == "lower") {
	return number - residue; 
    }
}

LL count (LL k, LL a, LL b) {
    LL out = 0;
    sharp_bound (k, &b);
    a = closest_multiplicity ("upper", a, k);
    b = closest_multiplicity ("lower", b, k);
    
    for (LL i = a; i <= b; i += k)
	out += check (i, k);
    
    return out;
}

void solve () {
    LL k, a, b;
    scanf ("%lld %lld %lld", &k, &a, &b);
    printf ("%lld\n", count (k, a, b));
}

LL brut (LL k, LL a, LL b) {
    LL out = 0;
    for (LL i = a; i <= b; ++i)
	out += check (i, k);
    return out;
}

void brut_test () {
    LL k, a, b;
    scanf ("%lld %lld %lld", &k, &a, &b);
    
    if (brut (k, a, b) == count (k, a, b))
	printf ("OK\n");
    else
	printf ("ZLE\n");
}

int main () {
    //brut_test ();
    solve ();
}