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
#include <cstdio>
#include <algorithm>
using namespace std;

const long long MAX_F = 18LL * 81;
const long long MAX_N = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;

int f(long long n) {
	int digit, res = 0;
	while(n > 0) {
		digit = n % 10;
		res += digit * digit;
		n /= 10;
	}
	return res;
}

bool check_equation(long long k, long long n) {
	int f_n = f(n);
	if (k > MAX_N / f_n)
		return false;
	return k * f_n == n;
}

bool in_range(long long n, long long a, long long b) {
	return n >= a && n <= b;
}

int main() {
	int res = 0;
	long long k, a, b, n;
	scanf("%lld%lld%lld", &k, &a, &b);

	for (int i = 1; i <= min(MAX_F, b/k); ++i) {
		n = i*k;
		if (check_equation(k, n) && in_range(n, a, b))
			res++;
	}

	printf("%d", res);
	return 0;
}