文件详细信息

下载本文件

本文件的大小为 818 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
int id[2521],tot,digits[25],cnt;
ll l,r;
ll f[25][50][2521];
ll dfs(int digit,int lcm,int num,int lim){
	if(digit==-1)return num%lcm==0;
	int id_lcm=id[lcm];
	if(!lim&&f[digit][id_lcm][num]!=-1)return f[digit][id_lcm][num];
	ll ans=0;
	int d=lim?digits[digit]:9;
	for(int i=0;i<=d;i++)ans+=dfs(digit-1,i?lcm/gcd(lcm,i)*i:lcm,(num*10+i)%2520,lim&&i==d);
	if(!lim)f[digit][id_lcm][num]=ans;
	return ans;
}
ll solve(ll n){
	cnt=0;
	while(n){
		digits[cnt++]=n%10;
		n/=10;
	}
	return dfs(cnt-1,1,0,1);
}
int main(){
	memset(f,-1,sizeof(f));
	for(int i=1;i<=2520;i++)
		if(2520%i==0)
			id[i]=++tot;
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld",&l,&r);
		printf("%lld\n",solve(r)-solve(l-1));
	}
	return 0;
}