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
import java.math.BigInteger;
import java.util.Scanner;

public class row {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    BigInteger k = BigInteger.valueOf(scanner.nextLong());
    BigInteger a = BigInteger.valueOf(scanner.nextLong());
    BigInteger b = BigInteger.valueOf(scanner.nextLong());
    scanner.close();

    int found = 0;

    for (int i = 1; i <= 9 * 9 * 18; i++) {
      BigInteger candidate = k.multiply(BigInteger.valueOf(i));
      if (isValid(candidate, k) && a.compareTo(candidate) <= 0 && candidate.compareTo(b) <= 0) {
        found++;
      }
    }
    System.out.println(found);
  }

  private static boolean isValid(final BigInteger candidate, BigInteger k) {
    return candidate.equals(BigInteger.valueOf(sumOfDigitSquares(candidate)).multiply(k));
  }

  private static long sumOfDigitSquares(BigInteger number) {
    long sum = 0;
    BigInteger stream = number;
    while (!stream.equals(BigInteger.ZERO)) {
      long digit = stream.mod(BigInteger.TEN).intValue();
      sum += digit * digit;
      stream = stream.divide(BigInteger.TEN);
    }
    return sum;
  }
}