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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class row {

	public static void main(String args[]) throws IOException {
		String line;
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		line = bufferedReader.readLine();
		String[] arr = line.split("\\s");
		System.out.println(doOneCase(Long.parseLong(arr[0]), Long.parseLong(arr[1]), Long.parseLong(arr[2])));
	}

	private static long doOneCase(long k, long a, long b) {
		int res = 0;
		for (long i = getStartValue(a, k); i <= b ; i = i+k) {
			if (f(i, k)) {
				res++;
			}
		}
		return res;
	}
	
	private static long getStartValue(long a, long k){
		long res = Math.max(a, k);
		long rest = res % k;
		return (rest == 0)?res:res+(k-rest);		
		
	}

	private static boolean f(long n, long k) {
				
		long limit = n / k;
		long res = 0;
		long current = n;

		long digit;
		
		while (current != 0) {
			digit = current % 10;
			res += digit * digit;
			current = current / 10;
			if(res > limit){
				return false;
			}
		}	
		return k * res == n;
	}

}