【题意】
定义C数为只包含数字2和9的数，求[L,R]内能被C数整除的个数。
【思路】
Dfs预处理出C数，并去除其中倍数的情况。
Dfs搜索出现情况，奇数加，偶数减，当数值大于R时剪枝。
【代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; typedef long long ll;
const int N = 2e3+; ll a[N],b[N],vis[N],ans,tot,n,L,R; void get_pre(int num)
{
if(num>R) return ;
if(num) a[++tot]=num;
get_pre(num*+);
get_pre(num*+);
}
ll gcd(ll a,ll b)
{
return b==? a:gcd(b,a%b);
}
void dfs(int cur,int cnt,ll lcm)
{
if(cur==n+) {
if(cnt&) ans+=R/lcm-(L-)/lcm;
else if(cnt) ans-=R/lcm-(L-)/lcm;
return ;
}
dfs(cur+,cnt,lcm);
ll val=lcm*a[cur]/(gcd(lcm,a[cur]));
if(val<=R) dfs(cur+,cnt+,val);
} int main()
{
scanf("%lld%lld",&L,&R);
get_pre();
sort(a+,a+tot+);
for(int i=;i<=tot;i++)
if(!vis[i]) {
b[++n]=a[i];
for(int j=i+;j<=tot;j++)
if(a[j]%a[i]==) vis[j]=;
}
for(int i=;i<=n;i++)
a[i]=b[n-i+];
dfs(,,);
printf("%lld\n",ans);
return ;
}