文件详细信息

下载本文件

本文件的大小为 1228 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
ll a,b,ans,f[18][30][19][13][11];
int g[]={2,3,5,7},k[]={0,0,0,0};
int fac[10][4]={{0,0,0,0},{0,0,0,0},{1,0,0,0},{0,1,0,0},{2,0,0,0},{0,0,1,0},{1,1,0,0},{0,0,0,1},{3,0,0,0},{0,2,0,0}};
ll dp(int digit,ll a,ll pot,ll L,ll R){
	ll b=a+pot-1;
	if(a>R||b<L)return 0;
	if(digit==18)return !k[0]&&!k[1]&&!k[2]&&!k[3];
	bool memoize=a>=L&&b<=R;
	if(memoize&&f[digit][k[0]][k[1]][k[2]][k[3]]>=0)return f[digit][k[0]][k[1]][k[2]][k[3]];
	pot/=10;
	ll ans=0;
	for(int d=(a!=0);d<=9;d++){
		bool divisible=true;
		for(int i=0;i<4;i++)
			if(fac[d][i]>k[i]){
				divisible=false;
				break;
			}
		if(!divisible)continue;
		for(int i=0;i<4;i++)k[i]-=fac[d][i];
		ans+=dp(digit+1,a+d*pot,pot,L,R);
		for(int i=0;i<4;i++)k[i]+=fac[d][i];
	}
	if(memoize)f[digit][k[0]][k[1]][k[2]][k[3]]=ans;
	return ans;
}
void dfs(ll product,int fac_id){
	if(product>1000000000ll||product*product>b)return;
	if(fac_id==4){
		ans+=dp(0,0,1000000000000000000ll,(a+product-1)/product,b/product);
		return;
	}
	dfs(product,fac_id+1);
	k[fac_id]++;
	dfs(product*g[fac_id],fac_id);
	k[fac_id]--;
}
int main(){
	memset(f,-1,sizeof(f));
	scanf("%lld%lld",&a,&b);
	dfs(1,0);
	printf("%lld\n",ans);
	return 0;
}