[bzoj2393] cirno's perfect math classroom

~Cirno Found a kind of baka Count , How about this number ~ Contains only 2 and ⑨ Two numbers ~~
Now? Cirno Want to know ~ In an interval ~~ How many numbers can be baka Integer division ~
however Cirno Such a genius goblin disdains to count
Only rely on smart you

A weakened version of SCOI2010 Lucky Numbers

Or consider the rapid growth rate of value, so it's good to tolerate violence

#include<bits/stdc++.h>
using namespace std;
typedef int INT;
#define int long long
int L,R;
int Baka[3000];
int vis[3000];
int A[3000];
int cnt=0;
void DFS(int x,int sum){
	if(sum>R)return;
	if(sum)Baka[++cnt]=sum;
	DFS(x+1,sum*10+2);
	DFS(x+1,sum*10+9);
}
int ans=0;
int GCD(int x,int y){
	while(y){
		int tmp=y;
		y=x%y;
		x=tmp;
	}
	return x;
}
void Solve(int x,int sum,int flag){
	if(sum<0||sum>R)return;
	if(x==A[0]+1){
		if(!sum)return;
		ans=(ans+(R/sum-L/sum)*flag);
		return;
	}
	int tmp;
	if(!sum)tmp=A[x];
	else tmp=sum/GCD(A[x],sum)*A[x];
	Solve(x+1,tmp,flag*-1);
	Solve(x+1,sum,flag);
}
bool cmp(int A,int B){
	return A>B;
}
signed main(){
	cin>>L>>R;
	L--;
	DFS(1,0);
	sort(Baka+1,Baka+1+cnt);
	for(int i=1;i<=cnt;++i){
		if(!vis[i])A[++A[0]]=Baka[i];
		for(int j=i+1;j<=cnt;++j){
			if(Baka[j]%Baka[i]==0)vis[j]=1;
		}
	}	
	sort(A+1,A+1+A[0],cmp);
	Solve(1,0,-1);
	cout<<ans;
}