题意:
定义幸运数为仅由数字6,8组成的数。
给定a,b,求$[a,b]$范围内有多少个幸运数的倍数。
$a,b\leq 10^{10}$。
题解:
首先暴力求一下幸运数,最多只有2000个左右。
然后容斥,但是发现复杂度是$2^{2000}$,希望不大。
我们考虑dfs式容斥,并添加如下三个剪枝:
- 对于两个幸运数x,y,如果y是x的倍数,那么去掉y。
- 对于当前的lcm,如果其超出上界,那么返回0。
- 将幸运数从大到小排序,使(2)更容易满足。
复杂度$O(能过)$。
套路:
- 形如$2^{n}$枚举复杂度过高$\rightarrow$改写成dfs并考虑剪枝。
代码:
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define ll unsigned long long #define rint register ll #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; ll dig[maxn],A[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline ll gcd(ll a,ll b){return (b==0)?a:gcd(b,a%b);} inline ll dfs(ll now,ll p,ll lcm,ll mx,ll end){ if(lcm>mx) return 0; if(now==end+1) return (lcm==1)?0:p*(mx/lcm); ll nlcm=A[now]*lcm/gcd(A[now],lcm); return dfs(now+1,p,lcm,mx,end)+dfs(now+1,p*(-1),nlcm,mx,end); } inline bool cmp(ll a,ll b){return a>b;} inline ll solve(ll n){ ll x=n,tot=0; while(x) dig[++dig[0]]=x%10,x/=10; for(ll i=1;i<=dig[0];i++){ for(ll j=0;j<(1ll<<i);j++){ ll num=0,w=1; for(ll k=0;k<i;k++,w=w*10){ if(j&(1ll<<k)) num+=w*8; else num+=w*6; } if(num<=n) A[++tot]=num; } } for(ll i=1;i<=tot;i++) for(ll j=1;j<=tot;j++){ if(A[j]==0 || A[i]==A[j]) continue; if(A[i]%A[j]==0){A[i]=0;break;} } sort(A+1,A+1+tot,cmp); while(A[tot]==0 && tot>=1) tot--; return dfs(1,-1,1,n,tot); } int main(){ ll a=read(),b=read(); printf("%lld\n",solve(b)-solve(a-1)); return 0; }幸运数字