在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“幸运号码”总是太少了,比如在[1,100]的区间内就只有6个(6,8,66,68,86,88),于是他又定义了一种“近似幸运号码”。lxhgww规定,凡是“幸运号码”的倍数都是“近似幸运号码”,当然,任何的“幸运号码”也都是“近似幸运号码”,比如12,16,666都是“近似幸运号码”。
现在lxhgww想知道在一段闭区间[a, b]内,“近似幸运号码”的个数。
Solution
套路,sum(b)-sum(a-1}。
问题变成了求1~x内的幸运数字个数。
我们先爆枚出6和8组成的数,排一遍序,把互为倍数的搞掉。
2^n枚举方案,当数目为奇数时加,否则减(容斥)。
Code
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; ll mm,tot,ji[3009],ans,tag,a,b,oo,top,bb[3009]; bool vis[3009]; ll gcd(ll x,ll y){return y?gcd(y,x%y):x;} void dfs1(ll x) { if(x>mm)return; ji[++tot]=x; dfs1(x*10+6); dfs1(x*10+8); } void dfs2(int x,ll lcm,int num) { if(lcm>mm)return; if(x>top) { if(num)if(num&1)ans+=(mm/lcm);else ans-=(mm/lcm); return; } dfs2(x+1,lcm,num); double d=ji[x]/gcd(ji[x],lcm); if(((double)d*lcm)<=(double)mm)dfs2(x+1,lcm*d,num+1); } ll calc(ll x) { mm=x;tot=ans=top=0; memset(vis,0,sizeof(vis)); dfs1(6);dfs1(8); sort(ji+1,ji+tot+1); for(int i=1;i<=tot;++i) if(!vis[i]) { bb[++top]=ji[i]; for(int j=i+1;j<=tot;++j) if(ji[j]%ji[i]==0)vis[j]=1; } for(int i=1;i<=top;++i) ji[i]=bb[top-i+1]; dfs2(1,1,0); return ans; } int main() { cin>>a>>b; cout<<calc(b)-calc(a-1); return 0; }