（上不了p站我要死了，侵权度娘背锅）
在用容斥定理时，常常会用到dfs的形式，如果枚举完所有的情况可能会超时，其剪枝的优化很是重要。
Description
~Cirno发现了一种baka数，这种数呢~只含有2和⑨两种数字~~
现在Cirno想知道~一个区间中~~有多少个数能被baka数整除~
但是Cirno这么天才的妖精才不屑去数啦
只能依靠聪明的你咯。
Input
一行正整数L R
( 1 < L < R < 10^10)
Output
一个正整数，代表所求的答案
Sample Input
1 100
Sample Output
58
像这种筛数的题很容易想到用容斥原理。
一个数的倍数-两个数的倍数+三个数的倍数……
我们发现，baka数一共有2^10个，但是其中有很多成倍数关系。于是就可以筛去不必要的数（倍数关系的数）。这要就可以减少很多数字了。
dfs时也有剪枝优化，如果此时的lcm已经大于上限，就可以return了。如果先枚举大的，可以减更多的枝。
排序前与排序后的对比
主要是练一下模板
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#ifdef WIN32
#define RIN "%I64d"
#else
#define RIN "%lld"
#endif
ll L,R;
ll num[1<<10],tp[1<<10],cnt1,cnt,ans;
void get_num(ll x){
if(x>R) return;
if(x*10+9<=R) tp[++cnt1]=x*10+9;//,printf("%d ",x*10+9);
get_num(x*10+9);
get_num(x*10+2);
}
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
void dfs(int step,ll now,ll lim,int state){
if(now>lim||step>cnt) return;
ll tmp=now*num[step]/gcd(now,num[step]);
ans+=lim/tmp*state;
dfs(step+1,tmp,lim,-state);
dfs(step+1,now,lim,state);
}
ll solve(ll x){
ans=0;
dfs(1,1,x,1);
return ans;
}
bool cmp(const ll &a,const ll &b){
return a>b;
}
int main(){
scanf(RIN,&L);
scanf(RIN,&R);
tp[++cnt1]=2;
get_num(0);
for(int i=1;i<=cnt1;i++){
bool bj=0;
for(int j=1;j<=cnt;j++)
if(tp[i]%num[j]==0){
bj=1;break;
}
if(!bj) num[++cnt]=tp[i];
}
sort(num+1,num+cnt+1,cmp);
ll ansl=solve(L-1);
ll ansr=solve(R);
printf(RIN"
",ansr-ansl);
return 0;
}