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
#include <iostream>
using namespace std;
const long long INF = (1LL<<60);
const int MOD = 2520;
int len(long long x) {
    int res = 1;
    while (x /= 10) res++;
    return res;
}
long long pow(int a, int n) {
    long long res = 1;
    while (n--) res *= a;
    return res;
}
bool is_allowed_digit[10], is_allowed_rest[MOD];
long long cache[19][MOD];
long long f(int len, long long max=INF, int rest=0) {
    if (len == 0) return is_allowed_rest[rest];
    if (max >= pow(10, len) && cache[len][rest] != -1) return cache[len][rest];
    long long res = 0;
    for (int d=1; d<=9; d++) {
        if (!is_allowed_digit[d]) continue;
        long long val = d * pow(10, len-1);
        if (val >= max) break;
        res += f(len-1, max-val, (rest + val) % MOD);
    }
    if (max >= pow(10, len)) cache[len][rest] = res;
    return res;
}
int main() {    
    long long l, r;
    cin >> l >> r;
    int ll = len(l), lr = len(r);
    long long res = 0;

    is_allowed_digit[1] = true;
    for (int i=0; i<(1<<8); i++) {
        for (int i=0; i<=18; i++)
            for (int j=0; j<MOD; j++) cache[i][j] = -1;

        for (int j=0; j<8; j++) is_allowed_digit[j+2] = (i&(1<<j));
        int allowed_rests = 0;
        for (int r=0; r<MOD; r++) {
            is_allowed_rest[r] = true;
            for (int d=2; d<=9; d++) if ((r%d == 0) != (is_allowed_digit[d])) is_allowed_rest[r] = false;
            allowed_rests += is_allowed_rest[r];
        }
        if (allowed_rests == 0) continue;
        res += f(lr, r+1) - f(ll, l);
        for (int i=ll; i<lr; i++) res += f(i);
    }

    cout << res << "\n";
    return 0;
}