https://www.lydsy.com/JudgeOnline/problem.php?id=1853
https://www.lydsy.com/JudgeOnline/problem.php?id=2393
以前者为标准讲题。
在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。 现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。
这题如果不说暴力大家估计就都掉到数位dp的坑里了，然而显然我们也没法判断倍数关系是不是。
暴力搜一遍发现幸运数字很少，如果把相互为倍数的幸运数字删掉的话只有1000左右。
容斥一遍（1个数的倍数个数-2个数+3个数……）
优化：将数从大到小排序以此让lcm增长变快，然后当lcm>r时跳出。
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef long double dl;
const int N=;
const int dig1=;
const int dig2=;
ll l,r,a[N],ans,tot;
inline bool cmp(ll x,ll y){return x>y;}
void init(ll x){
if(x>r)return;
if(x>)a[++tot]=x;
init(x*+dig1);
init(x*+dig2);
}
ll gcd(ll x,ll y){
return y?gcd(y,x%y):x;
}
void dfs(int now,int sum,ll k){
if(now>tot){
if(!sum)return;
ans+=((sum&)?:-)*(r/k-(l-)/k);
return;
}
dfs(now+,sum,k);
if((dl)k/gcd(k,a[now])<=(dl)r/a[now])
dfs(now+,sum+,k*a[now]/gcd(k,a[now]));
}
int main(){
scanf("%lld%lld",&l,&r);
init();sort(a+,a+tot+,cmp);
int tmp=;
for(int i=;i<=tot;i++){
for(int j=i+;j<=tot&&a[i];j++){
if(!a[j])continue;
if(a[i]%a[j]==)a[i]=;
}
if(a[i])a[++tmp]=a[i];
}
tot=tmp;
dfs(,,);
printf("%lld\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++