题目概述

问 $[L,R]$ 多少个整数是每个位上的数的倍数（$0$ 不算）。

解题报告

这道题想法不是特别难，但是要考虑优化。

首先可以发现只需要记录 $mod\ 5,mod\ 7,mod\ 8,mod\ 9$ 四个值（也就是 $mod\ 2520$ 的值）以及数的出现状态 $s$ 就行了，但是时间复杂度不能承受。可以把 $s$ 改成每个位上的数的 $lcm$，这样看起来状态变多了，实际上打个表会发现 $[1,9]$ 随意组合出的 $lcm$ 只有 $50$ 个左右，记录一下就行了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=20,MOD=2520,maxs=1<<9;

LL L,R,f[maxn+5][MOD][maxs+5];int te,a[maxn+5],S[maxs],tot,ID[maxs],vis[MOD+5];

LL Dfs(int i,int M,int s,bool fl){
    if (!i) return !(M%S[s]);if (!fl&&~f[i][M][ID[s]]) return f[i][M][ID[s]];LL ans=0;
    for (int j=0,MAX=(fl?a[i]:9);j<=MAX;j++) ans+=Dfs(i-1,(M*10+j)%MOD,j?(s|1<<j-1):s,fl&&j==MAX);
    if (!fl) f[i][M][ID[s]]=ans;return ans;
}
inline LL Solve(LL x){
    a[0]=0;do a[++a[0]]=x%10,x/=10; while (x);
    return Dfs(a[0],0,0,true);
}
int gcd(int a,int b) {if (!b) return a;return gcd(b,a%b);}
inline int lcm(int x,int y) {return x/gcd(x,y)*y;}
inline int LCM(int s) {int S=1;for (int i=0;i<9;i++) if (s>>i&1) S=lcm(S,i+1);return S;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    memset(f,255,sizeof(f));for (int i=0;i<maxs;i++) S[i]=LCM(i);
    for (int i=0;i<maxs;i++) vis[S[i]]?ID[i]=vis[S[i]]:ID[i]=vis[S[i]]=++tot;
    for (scanf("%d",&te);te;te--){
        scanf("%lld%lld",&L,&R);
        printf("%lld\n",Solve(R)-Solve(L-1));
    }
    return 0;
}