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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(ll x){
    ll y=x;
    if(!x)return 0;
    while(x>0){
        if((x%10)==0)return 0;
        if(y%(x%10))return 0;
        x/=10;
    }
    return 1;
}
bool czy[1000];
int S[1000], T[1000], S2[3];
ll dp[16][63][1000][3][2][2][2];
vector<int> V;
ll solve(ll x){
    ll ans=0;
    while(x%1000){
        //cout<<x;
        ans+=check(x);
        x--;
    }
    //return ans;
    ll f=x;
    int j=-3;
    vector<int> V2;
    while(f>0){
        V2.push_back(f%10);
        f/=10;
    }
    reverse(V2.begin(), V2.end());
    f=1;
    ans+=check(x);
    while(V2.size()){
        //cout<<V2.back()<<" ";
        if(V2.back()==0){
            V2.pop_back();
            j++;
            f*=10;
            continue;
        }
        //cout<<j<<" "<<ans<<"\n";
        V2[V2.size()-1]--;
        if(V2.back()==0 && V2.size()==1)break;
        x-=f;
        //cout<<x<<"\n";
        int a1=1, a2=1, a3=1, a4=1, a5=0;
        if(V2.size()>1 || V2.back()){
            for(int i:V2){
                if(i==9)a1=9;
                if(!(i%3))a1=max(a1, 3);
                if(i==7)a2=7;
                if(i==8)a3=8;
                if(i==4)a3=max(4, a3);
                if(i==2 || i==6)a3=max(2, a3);
                if(i==5)a4=5;
                if(i==0)a5=1;
            }
        }
        if(a5)continue;
        //cout<<"a";
        //cout<<x<<"\n";
        for(int i3:V){
            for(int i2=0; i2<63; i2++){
                if(i3%a4)continue;
                if(i3%a3)continue;
                for(int i4=0; i4<3; i4++){
                    for(int i5=0; i5<2; i5++){
                        if((i2+x)%max({a1, S[i3], S2[i4]})==0 && (i2+x)%max({a2, T[i3], 7*i5})==0){
                            ans+=dp[j][i2][i3][i4][i5][!!i4][!!i5];
                            //if(dp[j][i2][i3][i4][i5][!!i4][!!i5])cout<<j<<" "<<i2<<" "<<i3<<" "<<i4<<" "<<i5<<"\n";
                        }
                    }
                }
            }
        }
    }
    //cout<<x<<" "<<f<<" ";
    //return ans;
    while(x>1000){
        if(x-f==0){
            f/=10;
            j--;
            continue;
        }
        x-=f;
        int a1=1, a2=1, a3=1, a4=1, a5=0, i=x/f;
        if(i==9)a1=9;
        if(!(i%3))a1=max(a1, 3);
        if(i==7)a2=7;
        if(i==8)a3=8;
        if(i==4)a3=max(4, a3);
        if(i==2 || i==6)a3=max(2, a3);
        if(i==5)a4=5;
        if(i==0)a5=1;
        if(a5)continue;
        for(int i3:V){
            for(int i2=0; i2<63; i2++){
                if(i3%a4)continue;
                if(i3%a3)continue;
                for(int i4=0; i4<3; i4++){
                    for(int i5=0; i5<2; i5++){
                        if((i2+x)%max({a1, S[i3], S2[i4]})==0 && (i2+x)%max({a2, T[i3], 7*i5})==0){
                            ans+=dp[j][i2][i3][i4][i5][!!i4][!!i5];
                            //if(dp[j][i2][i3][i4][i5][!!i4][!!i5])cout<<j<<" "<<i2<<" "<<i3<<"\n";
                        }
                    }
                }
            }
        }
    }
    while(x>0)ans+=check(x--);
    return ans;
}
int main(){
    for(int i=100; i<1000; i++){
        int a=i/100, b=(i-100*a)/10, c=i%10;
        if(b==0 || c==0)continue;
        czy[i]=1;
        if(a%3 && a%7 && i%a)czy[i]=0;
        if(b%3 && b%7 && i%b)czy[i]=0;
        if(c%3 && c%7 && i%c)czy[i]=0;
        if((a==6 || b==6) && i%2)czy[i]=0;
        int s=0, t=0;
        if(!(a%3 && b%3 && c%3))s=1;
        if(a==9 || b==9 || c==9)s=2;
        if(!(a%7 && b%7 && c%7))t=1;
        if(czy[i])for(int j=0; j<3; j++)for(int k=0; k<2; k++)if(s<=j && t<=k)dp[0][i%63][i][j][k][(s==j)&&j][(t==k)&&k]=1;
        if(czy[i])V.push_back(i);
        S[i]=1;
        T[i]=1;
        if(t)T[i]=7;
        if(s==1)S[i]=3;
        if(s==2)S[i]=9;
    }
    ll f=1000;
    for(int i1=0; i1<15; i1++){
        for(int i2=0; i2<63; i2++){
            for(int i3:V){
                for(int i4=0; i4<3; i4++){
                    for(int i5=0; i5<2; i5++){
                        for(int i6=0; i6<2; i6++){
                            for(int i7=0; i7<2; i7++){
                                for(int d=1; d<10; d++){
                                    if(d==6 && (i3&1))continue;
                                    if(d==9){
                                        if(i4==2)dp[i1+1][(i2+d*f)%63][i3][i4][i5][1][i7]+=dp[i1][i2][i3][i4][i5][i6][i7];
                                    }
                                    else if(d==3 || d==6){
                                        if(i4==1)dp[i1+1][(i2+d*f)%63][i3][i4][i5][1][i7]+=dp[i1][i2][i3][i4][i5][i6][i7];
                                        if(i4==2)dp[i1+1][(i2+d*f)%63][i3][i4][i5][i6][i7]+=dp[i1][i2][i3][i4][i5][i6][i7];
                                    }
                                    else if(d==7){
                                        if(i5==1)dp[i1+1][(i2+d*f)%63][i3][i4][i5][i6][1]+=dp[i1][i2][i3][i4][i5][i6][i7];
                                    }
                                    else{
                                        if(i3%d==0)dp[i1+1][(i2+d*f)%63][i3][i4][i5][i6][i7]+=dp[i1][i2][i3][i4][i5][i6][i7];
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        f*=10;
    }
    S2[0]=1;
    S2[1]=3;
    S2[2]=9;
    //cout<<V.size()<<"\n";
    ll x, y;
    cin>>y>>x;
    //cout<<check(x);
    cout<<solve(x)-solve(y-1);
}