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
89
90
91
92
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int NUM_LIMIT = 19;
const int REM = 2520; // NWW of all digits except 0

ll mp[NUM_LIMIT + 1][1 << 9][2][REM];

ll dp(const vector<int>& num, int i, int encountered, int can_choose_any, int remainder) {
    ll& ans = mp[i][encountered][can_choose_any][remainder];
    if (ans != -1) return ans;

    if (i == num.size()) {
       bool ok = true;
       for(int i = 1; i < 10; i++) {
           if((1 << (i - 1)) & encountered) {
               if (remainder % i > 0) {
                   ok = false;
                   break;
               }
           }
       }
       ans = ok && encountered > 0 ? 1 : 0;
    } else {
        ans = 0;
        for(int d = 0; d < 10; d++) {
            if (can_choose_any == 0 && (num[i] < d)) continue;
            if (encountered > 0 && d == 0) continue;
            ans += dp(
                num,
                i + 1,
                d == 0 ? encountered : encountered | 1 << (d - 1),
                can_choose_any == 1 ? 1: d < num[i],
                (10 * remainder + d) % REM 
            );
        }
    }

    return ans;
}

ll solve(const ll l, const ll r) {
    vector<int> left, right;

    for(auto c : to_string(l - 1)) left.push_back(c - '0');
    for(auto c : to_string(r)) right.push_back(c - '0');

    memset(mp, -1, sizeof(mp));
    auto L = dp(left, 0, 0, 0, 0);
    memset(mp, -1, sizeof(mp));
    auto R = dp(right, 0, 0, 0, 0);
    // cout << "R: " << R << ", L: " << L << endl;
    return R - L;
}

ll brute(ll l, ll r) {
    int ans = 0;
    for(long x = l; x <= r; x++) {
        bool broken = false;
        auto xstr = to_string(x);
        for(auto c : xstr) {
            if (c - '0' == 0 || x % (c - '0') > 0) {
                broken = true;
                break;
            }
        }
        if(!broken) ans++;
    }
    return ans;
}

int main(int argc, char const *argv[]) {

    ll l, r;
    cin >> l >> r;
    cout << solve(l, r) << endl; 
    // int n = 1*1000*1000;
    // for(int l = 999965; l < n; l++) {
    //     for(int r = l; r < n; r++) {
    //        if(solve(l, r) == brute(l, r)) {
    //            cout << "\rok for l: " << l << ", r: " << r << flush;
    //        } else {
    //            cout << "bad for l" << l << ", r: " << r << endl;
    //        }
    //     }
    // }
    // cout << brute(l, r) << endl;
    return 0;
}