[SCOI2010]幸运数字

预处理出幸运数，把有倍数关系的两个数中较大的数删掉，从大到小排序组成真幸运数数列。

再用DFS来进行容斥。

区间查询[l,r]可以转换为 前缀r的值 减去 前缀l-1的值。

注意剪枝：当前要算贡献的数大于r时，退出。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,tot,l,r,ans;
int a[3000];
bool pd[3000];void dfs(int x,int sum)   //搜索原始数堆 
{if (x==11) {a[++n]=sum; return;}	dfs(x+1,sum*10+6);dfs(x+1,sum*10+8);
}int gcd(int a,int b)
{if (a%b==0) return b;return gcd(b,a%b); 
}void dfs(int x,int cnt,int now)
{if (now>r) return;if (x==tot+1){if (cnt&1ll) ans+=r/now-(l-1)/now;else ans-=r/now-(l-1)/now;return;}  
//考虑容斥：ans=一个数的lcm的贡献值-两个数的lcm的贡献值+三个数的lcm的贡献值-四个数的lcm的贡献值... if (1.0*now/gcd(now,a[x])*a[x]<=r) dfs(x+1,cnt+1,now/gcd(now,a[x])*a[x]);//注意要写个1.0,强转double，否则有可能爆longlong后，使得原来应该剪枝的部分也继续dfs了//导致超时 dfs(x+1,cnt,now);
}signed main(){for (register int i=1; i<=10; ++i) dfs(i,0);for (register int i=1; i<=n; ++i)for (register int j=1; j<=n; ++j) if (i!=j && a[i]%a[j]==0) {pd[i]=true; break;}for (register int i=1; i<=n; ++i) if (!pd[i]) a[++tot]=a[i];//使得原始数堆中 任意两数没有倍数关系 sort(a+1,a+tot+1);reverse(a+1,a+tot+1); //让大数在前面，可以使得少做几步，lcm就大于r，退出 scanf("%lld%lld",&l,&r);for (register int i=1; i<=tot; ++i) dfs(i+1,1,a[i]); //枚举所有的lcm printf("%lld\n",ans); 
return 0;	
}