经典数位DP
虽然题目给的n非常大，但是其实只有可能是质因子2357组成的数，所以事先打个表就行，总共是5000多个数。
然后就是做普通的数位DP，注意这里需要处理前导零，毕竟前导零对乘积是有影响的
下附代码：
1 #include<bits/stdc++.h> 2 #define ll unsigned long long 3 using namespace std; 4 vector<ll> cnt; 5 ll dp[20][6000][2]; 6 int dim[25]; 7 ll m; 8 ll qpow(ll a,ll b){ 9 ll ret=1; 10 while (b){ 11 if (b&1) ret=ret*a; 12 a=a*a; 13 b>>=1; 14 } 15 return ret; 16 } 17 void init(ll n){ 18 ll t2=0,t3=0,t5=0,t7=0; 19 cnt.push_back(0); 20 while (qpow(2,t2)*qpow(3,t3)*qpow(5,t5)*qpow(7,t7)<=n){ 21 while (qpow(2,t2)*qpow(3,t3)*qpow(5,t5)*qpow(7,t7)<=n){ 22 while (qpow(2,t2)*qpow(3,t3)*qpow(5,t5)*qpow(7,t7)<=n){ 23 while (qpow(2,t2)*qpow(3,t3)*qpow(5,t5)*qpow(7,t7)<=n){ 24 cnt.push_back(qpow(2,t2)*qpow(3,t3)*qpow(5,t5)*qpow(7,t7)); 25 t7++; 26 } 27 t7=0,t5++; 28 } 29 t3++,t5=0,t7=0; 30 } 31 t2++,t3=0,t5=0,t7=0; 32 } 33 sort(cnt.begin(),cnt.end()); 34 } 35 ll dfs(int x,int st,int jb,int fz){ 36 if (!x){ 37 return st!=0; 38 } 39 if (!jb && dp[x][st][fz]!=-1) return dp[x][st][fz]; 40 int maxn=9; 41 ll ret=0; 42 if (jb) maxn=dim[x]; 43 for (int i=0; i<=maxn; i++){ 44 if (cnt[st]*i>cnt[m-1]) continue; 45 if (fz==1 && i==0){ 46 ret+=dfs(x-1,st,(i==maxn && jb==1),fz); 47 } 48 else { 49 vector <ll>::iterator pos1=find(cnt.begin(),cnt.end(),cnt[st]*i); 50 int pos; 51 if(pos1!=cnt.end()) 52 pos=distance(cnt.begin(),pos1); 53 ret+=dfs(x-1,pos,(i==maxn && jb==1),0); 54 } 55 } 56 if (!jb) return dp[x][st][fz]=ret; 57 return ret; 58 } 59 int main(){ 60 ll n,l,r; 61 memset(dp,-1,sizeof(dp)); 62 scanf("%lld%lld%lld",&n,&l,&r); 63 init(n); 64 m=cnt.size(); 65 r--; 66 l--; 67 int len=0; 68 if (l==0){ 69 len=1; 70 dim[1]=0; 71 } 72 else while (l){ 73 dim[++len]=l%10; 74 l/=10; 75 } 76 ll resl=dfs(len,1,1,1); 77 len=0; 78 while (r){ 79 dim[++len]=r%10; 80 r/=10; 81 } 82 ll resr=dfs(len,1,1,1); 83 printf("%lld ",resr-resl); 84 }