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

#define MAX_SUM	1458
#define MAX_NUM	1000000000000000000LL

using namespace std;

long long getLowerLimit(long long k, long long a) {
	long long ret;
	if(a == 0)
		return 0;
	else if(k >= a)
		return k;
	else if(a > MAX_NUM - (k - (a % k)))
		return MAX_NUM + 1;
	else
		return a + (k - (a % k));
} 

long long getUpperLimit(long long k, long long b) {
	long long ret;
	if(k > MAX_NUM / 1500)
		return b;
	ret = 1500 * k;
	if(ret < b)
		return ret;
	return b;
} 

int getSquaresSum(long long n) {
	int ret = 0;
	while(n > 0) {
		int temp = n % 10;
		temp *= temp;
		ret += temp;
		n /= 10;
	}
	return ret;
}

bool isEquationValid(long long n, long long k) {
	int sumSquares = getSquaresSum(n);
	if(k > MAX_NUM / sumSquares)
		return false;
	return (k * sumSquares == n);		
}

int main() {
	long long a, b, k;
	cin >> k;
	cin >> a;
	cin >> b;
	long long lowLimit = getLowerLimit(k, a);
	long long highLimit = getUpperLimit(k, b);
	long long ret = 0;
	for(long long i = lowLimit; i<=highLimit; i+=k) {
		if(isEquationValid(i, k))
			ret++;
	}
	cout << ret << endl;
	return 0;
}