http://www.lydsy.com/JudgeOnline/problem.php?id=1853
题意：
在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。 现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。
思路：
首先要明白一点的是，在N范围内找a或b的倍数的个数为：
那么推广到这题的话也是差不多的，也就是容斥原理的运用。
首先可以先找出所有带6、8的数，可以优化一下删去有倍数关系的数，然后就是从中找lcm，也就是容斥原理的奇加偶减。在寻找的过程中，优先找值大的，这样一来剪枝会剪得更多一些。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + ; int n;
ll l, r;
ll cnt;
ll ans;
ll a[maxn];
ll b[maxn];
int vis[maxn]; void init(ll x)
{
if(x>r) return;
if(x!=) a[cnt++]=x;
init(x*+);
init(x*+);
} ll gcd(ll a, ll b)
{
return b==?a:gcd(b,a%b);
} void dfs(int cur, int cnt, ll val)
{
if(cur>=n)
{
if(!cnt) return;
if(cnt&) ans+=(r/val-(l-)/val);
else ans-=(r/val-(l-)/val);
return;
}
dfs(cur+,cnt,val);
ll tmp=val/(gcd(a[cur],val));
if((double)tmp*a[cur]<=r)
{
dfs(cur+,cnt+,tmp*a[cur]);
}
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%lld%lld",&l,&r))
{
cnt=;
init(); n=;
sort(a,a+cnt);
memset(vis,,sizeof(vis));
for(int i=;i<cnt;i++)
{
if(!vis[i])
{
b[n++]=a[i];
for(int j=i+;j<cnt;j++)
{
if(a[j]%a[i]==)
vis[j]=;
}
}
}
for(int i=;i<n;i++)
a[i]=b[n-i-]; ans=;
dfs(,,);
printf("%lld\n",ans);
}
return ;
}