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

int calcDigitsNumber(long long int number) {
	unsigned long long int checker = 10;
	int result = 1;
	while (checker <= number){
		checker *= 10;
		++result;
	}
	return result;
}

int calcSumOfSquareDigits(long long int number) {
	int result = 0;
	while (number > 0){
		int rem = (number % 10);
		result += rem*rem;
		number /= 10;
	}
	return result;
}

int main() {

	long long int k, a, b;

	std::cin >> k >> a >> b;

	int digitsA = calcDigitsNumber(a);
	int digitsB = calcDigitsNumber(b);

	long long int minv = std::max(k*digitsA, a);
	long long int maxv = std::min(k * 81 * digitsB, b);

	long long int remainder = minv%k;

	if (remainder != 0) minv += k - remainder;

	long long int val = minv;

	int result = 0;

	while (val <= maxv){
		if (k*calcSumOfSquareDigits(val) == val){
			++result;
		}
		val += k;
	}

	std::cout << result << std::endl;

	return 0;

}