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

using lld = long long int;
using llu = unsigned long long int;

int number_pos(llu n)
{
	int i = 0;
	while (n > 0)
	{
		n /= 10;
		++i;
	}
	return i;
}

llu sum_of_squares(llu n)
{
	llu sum = 0;
	while (n > 0)
	{
		llu i = n % 10;
		sum += i*i;
		n /= 10;
	}
	return sum;
}


int main()
{
	std::ios_base::sync_with_stdio(0);
	llu k = 0, a = 0, b = 0;
	std::cin >> k >> a >> b;

	// k * f(n) = n
	// f(n) = n/k

	llu range_min = std::max({k, a});
	llu range_max = std::min({k * number_pos(b) * 81, b});
	// std::cout << "[" << range_min << ", " << range_max << "]" << std::endl;
	llu start_point = range_min - (range_min % k);

	llu matched = 0;
	for (llu i = start_point; i <= range_max; i += k)
	{
		llu sos = sum_of_squares(i);
		if (sos * k == i)
		{
			// std::cout << i << std::endl;
			++matched;
		}
	}
	std::cout << matched << std::endl;
	return 0;
}