原题链接：https://www.luogu.com.cn/problem/P2567
题意解读：幸运数字由6和8组成，近似幸运数字是幸运数字的倍数，求[a,b]区间内近似幸运数字的个数。
解题思路：
通过暴搜可以枚举出所有的幸运数字。
不妨设幸运数字为x、y、z，显然，如果x、y、z中有互为倍数的，可以将其中的倍数去掉。
对于[a,b]中x的倍数，其个数为b/x-(a-1)/x，原理是：1~a-1中x的倍数个数为(a-1)/x，1~b中x的倍数个数为b/x，那么[a,b]中x的倍数个数为b/x-(a-1)/x。
我们可以得到[a,b]中x的倍数个数xcnt，y的倍数个数ycnt，z的倍数个数zcnt，xcnt+ycnt+zcnt里会出现重复计算，比如既是x又是y的倍数，
既是x又是y的倍数可以认为是lcm(x,y)的倍数，个数为xycnt=b/lcm(x,y)-(a-1)/lcm(x,y)，
同理，
既是y又是z的倍数个数为yzcnt=b/lcm(y,z)-(a-1)/lcm(y,z)，
既是x又是z的倍数个数为xzcnt=b/lcm(x,z)-(a-1)/lcm(x,z),
xcnt+ycnt+zcnt-xycnt-yzcnt-xzcnt中，对于同时是x、y、z的倍数的个数减多了，设xyzcnt=b/lcm(x,y,z)-(a-1)/lcm(x,y,z)
最后答案是xcnt+ycnt+zcnt-xycnt-yzcnt-xzcnt+xyzcnt。
原来这，是容斥原理。
推导到多个幸运数字的情况，可以用DFS来枚举所有的子集，再根据子集中个数奇偶来确定对答案的贡献是加还是减。
剪枝事项：
1、幸运数字从大到小排，倍数更快达到上限
2、倍数如果超过上限，不再继续DFS
3、幸运数字中有互为倍数的进行去重
注意事项：
计算LCM中可能会超过long long，需要用double
100分代码：
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
vector<LL> lucky1, lucky2; //所有幸运数字
bool del[1000000];
LL a, b, ans;void init(LL x)
{if(x > b) return;lucky1.push_back(x);init(x * 10 + 6);init(x * 10 + 8);
}LL GCD(LL a, LL b)
{return b == 0 ? a : GCD(b, a % b);
}double LCM(LL a, LL b) //注意计算LCM时可能会溢出，用double存储
{return 1.0 * a / GCD(a, b) * b;
}void dfs(int idx, LL cnt, LL lcm)
{if(lcm > b) return;if(idx == lucky2.size()){if(cnt == 0) return; //空集不考虑if(cnt % 2 == 1) ans += b / lcm - (a - 1) / lcm;else ans -= b / lcm - (a - 1) / lcm;return;}dfs(idx + 1, cnt, lcm); //不选当前幸运数字if(LCM(lcm, lucky2[idx]) <= b)dfs(idx + 1, cnt + 1, LCM(lcm, lucky2[idx]));//选当前幸运数字
}int main()
{cin >> a >> b;//生成所有幸运数字init(6);init(8);//排序，去掉倍数sort(lucky1.begin(), lucky1.end());for(int i = 0; i < lucky1.size(); i++){if(del[i]) continue;lucky2.push_back(lucky1[i]);for(int j = i + 1; j < lucky1.size(); j++){if(lucky1[j] % lucky1[i] == 0) del[j] = true;}}//从大到小排序reverse(lucky2.begin(), lucky2.end());//DFS枚举所有幸运数字组合的子集，容斥计算答案dfs(0, 0, 1);cout << ans;return 0;
}