？
by Keep_RAD @ 2021-07-17 19:08:14
@[achen126](/user/363069) 就是直接只把 $memset$ 更新一次，那下一组数据 $f$ 数组里的值不就不是 $-1$ 了吗
by _YangZj @ 2021-07-17 21:30:23
这是超时的代码，要怎么改啊
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define RI register int
#define RB register bool
#define ll long long
using namespace std;
const int maxn=25,maxm=2550;
int T,n,p[maxn],G[maxm],cnt;
ll f[maxn][maxm][50],l,r;
inline void init();
inline int lcm(RI,RI);
inline ll sol(ll);
inline ll dfs(RI,RI,RI,RB);
inline int gcd(RI,RI);
signed main() {
init();
cin>>T;
while(T--) {
cin>>l>>r;
cout<<sol(r)-sol(l-1)<<endl;
}
return 0;
}
inline int gcd(RI a,RI b) { if(a<b) swap(a,b); return !b?a:gcd(b,a%b); }
inline int lcm(RI a,RI b) { return a/gcd(a,b)*b; }
inline ll sol(ll x) {
memset(f,-1,sizeof(f)); n=0;
while(x) { p[++n]=x%10; x/=10; }
return dfs(1,0,1,1);
}
inline ll dfs(RI pos,RI res,RI lc,RB lim) {
if(pos>n) return (ll)(res%lc==0);
if(!lim && f[pos][res][G[lc]]!=-1) return f[pos][res][G[lc]];
RI up=lim?p[n-pos+1]:9;
ll sum=0;
for(RI i=0;i<=up;i++)
sum+=dfs(pos+1,(res*10+i)%2520,(!i)?lc:lcm(lc,i),(lim && i==up));
if(!lim) f[pos][res][G[lc]]=sum;
return sum;
}
inline void init() {
for(RI i=1;i<=2520;i++) if(2520%i==0) G[i]=++cnt;
}
```
by _YangZj @ 2021-07-17 21:32:09
%%%%
by Kanbe_Kotori @ 2021-07-18 00:13:41
在不受lim条件限制时，f[n-pos][res][G[lc]] 一样时，“很妙的数字”数显然是相等的。
by Kanbe_Kotori @ 2021-07-18 01:01:15
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define RI register int
#define RB register bool
#define ll long long
using namespace std;
const int maxn=25,maxm=2550;
int T,n,p[maxn],G[maxm],cnt;
ll f[maxn][maxm][50],l,r;
inline void init();
inline int lcm(RI,RI);
inline ll sol(ll);
inline ll dfs(RI,RI,RI,RB);
inline int gcd(RI,RI);
signed main() {
init();
cin>>T;
while(T--) {
cin>>l>>r;
cout<<sol(r)-sol(l-1)<<endl;
}
return 0;
}
inline int gcd(RI a,RI b) { if(a<b) swap(a,b); return !b?a:gcd(b,a%b); }
inline int lcm(RI a,RI b) { return a/gcd(a,b)*b; }
inline ll sol(ll x) {
n=0;
while(x) { p[++n]=x%10; x/=10; }
return dfs(1,0,1,1);
}
inline ll dfs(RI pos,RI res,RI lc,RB lim) {
if(pos>n) return (ll)(res%lc==0);
if(!lim && f[n-pos][res][G[lc]]!=-1) return f[n-pos][res][G[lc]];
RI up=lim?p[n-pos+1]:9;
ll sum=0;
for(RI i=0;i<=up;i++)
sum+=dfs(pos+1,(res*10+i)%2520,(!i)?lc:lcm(lc,i),(lim && i==up));
if(!lim) f[n-pos][res][G[lc]]=sum;
return sum;
}
inline void init() {
memset(f,-1,sizeof(f));
for(RI i=1;i<=2520;i++) if(2520%i==0) G[i]=++cnt;
}
//这样就AC了，跑的时间是我自己屑代码的1/3.。。
```
by Kanbe_Kotori @ 2021-07-18 01:05:40
@[Adp_D](/user/370216) 感谢神仙指导
by _YangZj @ 2021-07-18 08:33:29