超时了。。。。
by 小超手123 @ 2023-06-08 14:58:28
@[小超手123](/user/490978) 不用 reverse，倒着 DP，然后不要每次 memset
by 5k_sync_closer @ 2023-06-08 15:56:23
@[小超手123](/user/490978) 这样做的话 limit 就不能开在状态里，要记搜的时候特判，因为每次上限不一样
by 5k_sync_closer @ 2023-06-08 15:57:14
@[5k_sync_closer](/user/388651) 为什么不要每次 memset
by 小超手123 @ 2023-06-08 16:04:05
@[5k_sync_closer](/user/388651) 改成这样了，但是WA了
```cpp
#include<bits/stdc++.h>
using namespace std;
int T;
int P[2530], Q[50], tot;
long long f[20][2522][49];
//f[i][j][k][l] 表示前 i 位，当前数 % 2520 = j , 最大公倍数 = k , l：卡没卡住
int A[20], num;
int gcd(int x, int y) {
if(y == 0) return x;
return gcd(y, x % y);
}
int lcm(int x, int y) {
return x * y / gcd(x, y);
}
long long dfs(int Pos, int now, int S, int lim) {
if(Pos == 0) {
if(now % Q[S] == 0) return 1;
else return 0;
}
if(f[Pos][now][S] != -1 && lim == 0) return f[Pos][now][S];
long long ans = 0;
for(int i = 0; i <= (lim == 1 ? A[Pos] : 9); i++)
ans += dfs(Pos - 1, (now * 10 + i) % 2520, P[i == 0 ? Q[S] : lcm(Q[S], i)], (i == A[Pos]) && lim);
if(lim == 0)f[Pos][now][S] = ans;
return ans;
}
long long Sol(long long x) {
num = 0;
while(x) {
A[++num] = x % 10;
x /= 10;
}
return dfs(num, 0, 0, 1);
}
signed main() {
Q[0] = 1;
for(int i = 1; i <= 2520; i++)
if(2520 % i == 0) P[i] = ++tot, Q[tot] = i;
// cout << tot << endl;
cin >> T;
while(T--) {
long long l, r;
cin >> l >> r;
cout << Sol(r) - Sol(l - 1) << endl;
}
return 0;
}
```
by 小超手123 @ 2023-06-08 16:15:48
@[小超手123](/user/490978) 你至少在 main 最开始 memset 一次吧……
by 5k_sync_closer @ 2023-06-08 16:23:01
@[5k_sync_closer](/user/388651) 谢了
by 小超手123 @ 2023-06-08 16:30:27