55 D Beautiful numbers

問題

t組の二つの自然数の組l[i],r[i]が与えられる。
それぞれに対して、l[i]以上r[i]以下で、かつ以下の条件を満たす数の数を求めよ。

• 0以外の各桁で、その数が割り切れる

制約条件

t≦10
l[i],r[i]≦9*10^18

方針

95 D Horse Racesとほぼ同じ。
各桁でその和が割り切れる数というのは、DPで、
「いままでに出現した1〜9のフラグ」、「いままでの数のmod2520でのあまり」を
覚えながらテーブルを更新することで求まる。

見ている数より小さい数になった場合メモ化をし、そうでないときはメモ化をしないことでDPテーブルが全てのl[i],r[i]について使いまわせるようになる。

ソースコード

ll dp[20][2520][4*3*2*2];//2(3乗まで), 3(2乗まで), 5(1乗まで), 7(1乗まで)

ll rec(char *s,int p,int mod,int e,bool small){

	if(small&&dp[p][mod][e]>=0)return dp[p][mod][e];
	int two=e%4, three=e/4%3, five=e/12%2, seven=e/24;
	
	if(p==19){
		int tmp=1;
		rep(i,two)tmp*=2; rep(i,three)tmp*=3; rep(i,five)tmp*=5; rep(i,seven)tmp*=7;
		return mod%tmp==0;
	}
	
	ll ret=0;
	rep(i,10){
		int nmod=(mod*10+i)%2520, ne;
		bool nsmall=small||i<s[p]-'0';
		int t2=0,t3=0,t5=0,t7=0;
		for(int m=i;m&&m%2==0;m/=2)t2++;
		for(int m=i;m&&m%3==0;m/=3)t3++;
		for(int m=i;m&&m%5==0;m/=5)t5++;
		for(int m=i;m&&m%7==0;m/=7)t7++;
		t2=max(two,t2); t3=max(three,t3); t5=max(five,t5); t7=max(seven,t7);
		ne=t2+t3*4+t5*12+t7*24;
		
		if(nsmall||i==s[p]-'0')ret+=rec(s,p+1,nmod,ne,nsmall);
	}
	if(small)dp[p][mod][e]=ret;
	return ret;
}
void run()
{
	memset(dp,-1,sizeof(dp));
	int t; cin>>t;
	rep(i,t){
		ll a,b; cin>>a>>b; a--;
		char A[20],B[20];
		sprintf(A,"%019I64d",a); sprintf(B,"%019I64d",b);
		cout<<rec(B,0,0,0,0)-rec(A,0,0,0,0)<<endl;
	}
}