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
| #include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int popcount(int x) {
int sum=0;
while (x) x/=10,sum++;
return sum;
}
const int base=1e9;
map<int,int> f[19],vis[19];
int L,R,prime[5]={0,2,3,5,7};
int pw[20],ans;
int solve(int now,int sum,int r,int lim) {
if (now==0) {
if (sum==1) return 1;
return 0;
}
if (!lim&&vis[now][sum]) return f[now][sum];
int res=0,i;
for (i=1;i<=(lim?r/pw[now-1]%10:9);i++) if (sum%i==0) {
res+=solve(now-1,sum/i,r,lim&(i==r/pw[now-1]%10));
}
if (!lim) f[now][sum]=res,vis[now][sum]=1;
return res;
}
int total;
void calc(int sum) {
++total;
int l=(L+sum-1)/sum,r=R/sum,i;
if (r==0) return ;
int tmp=popcount(r);
for (i=1;i<tmp;i++) ans+=solve(i,sum,r,0);
ans+=solve(tmp,sum,r,1);
l=max(l-1,0ll);
if (!l) return ;
tmp=popcount(l);
for (i=1;i<tmp;i++) ans-=solve(i,sum,l,0);
ans-=solve(tmp,sum,l,1);
}
void dfs(int now,int sum) {
if (sum>base) return ;
if (now==5) return calc(sum),void();
for (int i=1;i<=30;i++) {
if (sum<base) dfs(now+1,sum);
else return ;
sum=sum*prime[now];
}
}
signed main(void){
int i;
read(L),read(R);
for (pw[0]=1,i=1;i<=18;i++) pw[i]=pw[i-1]*10;
dfs(1,1);
printf("%lld",ans);
return 0;
}
|