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
63
64
65
import java.util.ArrayList;
import java.util.Collection;
import java.util.Scanner;


public class row {
	
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			long k = scanner.nextLong();
			long beginRange = scanner.nextLong();
			long endRange = scanner.nextLong();
			
			NsFinder nsFinder = new NsFinder(k, beginRange, endRange);
			Collection<Long> ns = nsFinder.findNs();
			
			System.out.print(ns.size());
		};
	}

	private static class NsFinder {
		private long k;
		private long beginRange;
		private long endRange;
		
		public NsFinder(long k, long beginRange, long endRange) {
			this.k = k;
			this.beginRange = beginRange;
			this.endRange = endRange;
		}
		
		public Collection<Long> findNs() {
			Collection<Long> ns = new ArrayList<>();
			
			int minSum = 1;
			int maxSum = 17 * 9 * 9;
			
			for(int sum = minSum;sum <= maxSum;sum++) {
				if(Long.MAX_VALUE / k >= sum) {
					long n = sum * k;
					if(isWithinRange(n) && calculateSum(n) == sum) {
						ns.add(n);
					}
				}
			}
			
			return ns;
		}
		
		private boolean isWithinRange(long n) {
			return n >= beginRange && n <= endRange;
		}
		
		private int calculateSum(long n) {
			int sum = 0;
			while(n > 0) {
				int digit = (int)(n % 10);
				sum += digit * digit;
				n /= 10;
			}
			
			return sum;
		}
	}
}