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
#include <iostream>
#include <cmath>
using namespace std;

typedef long long int lli;

const int kw[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 };
const int mksize = 19;
const lli mink[] = { 1, 1, 1, 4, 25, 206, 1764, 15433, 137175, 1234568,
11223345, 102880659, 949667617, 8818342152, 82304526749,
771604938272, 7262164124910, 68587105624143, 649772579597141 };

lli a, b, k, i, n, s = 0;
double dycha = 10.0;

int dgt(lli n)
{
	const int d = 10; int s = 0;
	while (n >= d) {
		s += kw[n%d];
		n /= d;
	}
	return s + kw[n];
}

void row(lli k, lli a, lli b)
{
	s = 0;
	if (k == 1) {
		cout << 1 << endl;
		return;
	}

	i = a / k;
	n = i*k;
	if (n < a) n = ++i * k;

	//ograniczniki
	int odp = 0;
	for (int idx = 0; idx < mksize; idx++) {
		if (k >= mink[idx]){
			odp = idx + 1;
		}
		else
			break;
	}
	if (odp > mksize - 1)
		odp = mksize - 1;

	lli max = lli(pow(dycha, odp));
	if (b > max) {
		b = max;
	}

	lli min = lli(pow(dycha, floor(log10(double(k)))));
	if (a < min){
		a = min;
		i = a / k;
		n = i*k;
		if (n < a) n = ++i * k;
	}

	while (n <= b) {
		if (dgt(n) == i)
			s += 1;
		n = ++i * k;
	}

	cout << s << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> k >> a >> b;
	row(k, a, b);
	return 0;
}