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

public class row {
    public static final int MAX_DIGITS = 18;
    public static final int MAX_FN = 9 * 9 * MAX_DIGITS;

    public static void main(String[] args) {
        /** Read input */
        Scanner scanner = new Scanner(System.in);
        long k = Long.valueOf(scanner.next());
        long a = Long.valueOf(scanner.next());
        long b = Long.valueOf(scanner.next());
        scanner.close();

        /** Calculate digits */
        long digits[] = new long[MAX_DIGITS];
        long value = 1;
        for (int d = 0; d < MAX_DIGITS; d++) {
            digits[d] = value;
            value *= 10;
        }

        /** Calculate solutions */
        BigInteger big_b = BigInteger.valueOf(b);
        long solutions = 0;

        for (int fn = 1; fn <= MAX_FN; fn++) {
            BigInteger big_n = BigInteger.valueOf(k).multiply(BigInteger.valueOf(fn));

            /** Omit bigger values than limit */
            if (big_n.compareTo(big_b) > 0) {
                continue;
            }

            long n = k * fn;

            /** Omit lower values than limit */
            if (n < a) {
                continue;
            }

            /** Calculate sum of square of digits */
            long checked_fn = 0;
            long remain = n;
            long cyfra;
            for (int d = MAX_DIGITS - 1; d >= 0; d--) {
                cyfra = remain / digits[d];
                checked_fn += cyfra * cyfra;
                remain -= cyfra * digits[d];
            }

            /** Veryfication equality of sums */
            if (checked_fn == fn) {
                solutions++;
            }
        }

        /** Save output */
        System.out.print(solutions);
    }

}