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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <set>

bool isPotyczkowa(long long liczba) {
    long long tmp = liczba;
    bool isPotyczkowa = liczba > 0;
    while (isPotyczkowa && tmp > 0) {
        long long int digit = tmp % 10;
        tmp = (long long) (tmp / 10);
        isPotyczkowa = digit != 0 && liczba % digit == 0;
    }
    return isPotyczkowa;
}

static const long long POW[18] = {1,
                                  10,
                                  100,
                                  1000,
                                  10000,
                                  100000,
                                  1000000,
                                  10000000,
                                  100000000,
                                  1000000000,
                                  10000000000,
                                  100000000000,
                                  1000000000000,
                                  10000000000000,
                                  100000000000000,
                                  1000000000000000,
                                  10000000000000000,
                                  100000000000000000
};

bool isAllowed(int digit, long long number) {
    if (number == 0) {
        return true;
    }
    if (digit % 2 == 0 && 0 != number % 2) {
        return false;
    }
    if (digit %4 == 0 && number > 100 && number%4 != 0) {
        return false;
    }
    if (digit %8 == 0 && number > 1000 && number%8 != 0) {
        return false;
    }
    if (digit == 5 && (number % 2 == 0 || (number > 5 && number % 10 != 5))) {
        return false;
    }
    return true;
}

void countPotyczkow(long long &steps, long long min, long long max, long long &count, long long number, int pos) {
     steps++;
    if (number <= max) {
        if (number >= min and isPotyczkowa(number)) {
            count++;
        }
        for (int i = 1; i <= 9; i++) {
            long long int next = POW[pos] * i + number;

            if (next <= max && isAllowed(i, number)) {
                countPotyczkow(steps, min, max, count, next, pos + 1);
            }
        }
    }
}


int main() {
    long long l = 0;
    long long r = r;
    long long count = 0;
    long long steps = 0;
    std::cin >> l >> r;
    if(r-l <= POW[6]){
        while(l <=r) {
            if(isPotyczkowa(l++)) {
                count++;
            }
        }
    } else {
        countPotyczkow(steps, l, r, count, 0, 0);
    }
    std::cout << count << std::endl;
    return 0;
}