文件详细信息

下载本文件

本文件的大小为 2204 字节。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a<0)putchar('-'),a=-a;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
typedef long long ll;
const int sz=4,p[sz]={2,3,5,7};
const int maxcnt=5194,maxhash=55*37*19*19;
ll n,l,r;
int cnt;
struct Data{
	ll x;
	int a[sz];
}num[maxcnt],fac[10]={{0,0,0,0,0},{1,0,0,0,0},{2,1,0,0,0},{3,0,1,0,0},{4,2,0,0,0},{5,0,0,1,0},{6,1,1,0,0},{7,0,0,0,1},{8,3,0,0,0},{9,0,2,0,0}};
bool operator<(const Data a,const Data b){
	return a.x<b.x;
}
Data operator*(const Data&a,const Data&b){
	Data ans;
	ans.x=a.x*b.x;
	for(int i=0;i<sz;i++)ans.a[i]=a.a[i]+b.a[i];
	return ans;
}
Data operator/(const Data&a,const Data&b){
	Data ans;
	ans.x=a.x/b.x;
	for(int i=0;i<sz;i++)ans.a[i]=a.a[i]-b.a[i];
	return ans;
}
int digit[18],len;
std::set<Data>s[18];
void init_dfs(int cur,int lim,int zero,Data now){
	if(s[cur].find(now)!=s[cur].end())return;
	s[cur].insert(now);
	if(cur==0)return;
	int d=lim?digit[cur-1]:9;
	if(zero)init_dfs(cur-1,lim&&d==0,1,now);
	for(int i=1;i<=d&&(ll)now.x*i<=n;i++)init_dfs(cur-1,lim&&i==d,0,now*fac[i]);
}
ll f[18][maxhash];
ll cnt_dfs(int cur,int lim,int zero,Data now){
	if(cur==-1)return now.x==1?1:0;
	int id=((now.a[0]*37+now.a[1])*19+now.a[2])*19+now.a[3];
	if(!lim&&!zero&&f[cur][id]!=-1)return f[cur][id];
	ll ans=0;
	int d=lim?digit[cur]:9;
	if(zero&&cur>0)ans+=cnt_dfs(cur-1,lim&&d==0,1,now);
	for(int i=1;i<=d;i++)
		if(now.x%i==0)
			ans+=cnt_dfs(cur-1,lim&&i==d,0,now/fac[i]);
	if(!lim&&!zero)f[cur][id]=ans;
	return ans;
}
ll solve(ll x){
	if(!x)return 0;
	len=0;
	while(x){
		digit[len++]=x%10;
		x/=10;
	}
	for(int i=0;i<=len;i++)s[i].clear();
	init_dfs(len,1,1,Data{1,{0,0,0,0}});
	cnt=0;
	for(Data i:s[0])num[cnt++]=i;
	memset(f,-1,sizeof(f));
	ll ans=0;
	for(int i=0;i<cnt;i++)ans+=cnt_dfs(len-1,1,1,num[i]);
	return ans;
}
int main(){
	read(n),read(l),read(r);
	write(solve(r-1)-solve(l-1)),putchar('\n');
	return 0;
}