自动搬运

查看原文

来自洛谷，原作者为

	L_zaa_L And in case i don't see you,good afternoon,good evening,and good night

搬运于2025-08-24 22:45:17，当前版本为作者最后更新于2024-10-12 09:34:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数位 DP 题。

数位 DP 感觉都是一个样子的，然后我最喜欢用的是记忆化搜索（写得方便）。

我们需要记录的东西是他所有出现数字的最小公倍数，然后以及这个数的值，和有没有顶到上界。但是由于要有原数要整除最小公倍数，所以我们不能出现除前导 $0$ 以外的 $0$。而且我们发现我们记录的这个数是不好记忆化搜索的（会超时），由于有个东西就是 $x\bmod y=x\bmod y\bmod z(y\mid z)$，所以我们取模所有非零阿拉伯数字的最小公倍数 $2520$，然后再判断能不能整除，这样子就可以记忆化搜索了。

Code

#include<bits/stdc++.h>
#define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5,base=999983,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline void Add(int &x,int y){(x=x+y+Mod)%=Mod;}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
int a[N],tot;
map<tuple<int,int,int>,int>mp;
int  Gcd[3005];
int dfs(int x,int op,bool flag,int lcm,int yu){
	if(!op&&!flag&&mp.count(make_tuple(x,Gcd[lcm],yu))) return mp[make_tuple(x,Gcd[lcm],yu)];
	if(x==0){
//		if(yu%Gcd[lcm]==0) cout<<yu<<endl;
		return (yu%Gcd[lcm]==0);
	}
	int res=0;
	For(j,0,9){
		if(op&&j>a[x]) continue;
		if(!flag&&j==0) continue;
		res+=dfs(x-1,op&(j==a[x]),flag&(j==0),(j==0)?0:lcm|(1<<(j-1)),(yu*10+j)%2520);
	}
	if(!op&&!flag)mp[make_tuple(x,Gcd[lcm],yu)]=res;
	return res;
}
inline int calc(int x){
	int p=x;
	tot=0;
	mp.clear();
	while(p){
		a[++tot]=p%10;
		p/=10;
	}
	return dfs(tot,1,1,0,0);
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	int l=read(),r=read();
	For(i,0,1023){
		Gcd[i]=1;
		For(j,1,9){
			if(i&(1<<(j-1))) Gcd[i]=Gcd[i]*j/__gcd(Gcd[i],j);
		}
	}
	printf("%lld\n",calc(r)-calc(l-1));
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}