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
#include <cstdio>

int ord(unsigned long long n)
{
	int tens = 0;

	while (n > 0) {
		tens++;
		n /= 10;
	}

	return tens;
}

int main()
{
	unsigned long long a, b, k;
	unsigned long long sum = 0;
	unsigned long long max = 18 * 81;
	unsigned long long left, right;

	scanf("%llu %llu %llu", &k, &a, &b);
	
	left = right = b + 1;
	if ((k >= (a / max)) && (k <= b)) {
		if (k < a) {
			left = a - (a % k);
			if (a % k) {
				left += k;
			}
		} else {
			left = k;
		}
		if (ord(left) + ord(max) <= ord(b) + 1) {
			right = left * max;
		}
		if (right > b) {
			right = b;
		}
	}

	for (unsigned long long i = left; i <= right; i += k) {
		unsigned long long n = i;
		unsigned long long roots = 0;
		while (n > 0) {
			roots += (n % 10) * (n % 10);
			n /= 10;
		}
		if (ord(roots) + ord(k) <= ord(b) + 1) {
			if (roots * k == i) {
				sum++;
			}
		}
	}

	printf("%llu\n", sum);
}