P2567 SCOI2010 幸运数字

· · 题解

P2567幸运数字

Description

计算 [l,r] 之间有多少个数满足含 6 或含 8，或者是含 6 或含 8 的数的倍数。

Solution

容斥。

我们要先找出幸运数字，才能检索近似幸运数字。这一部分直接跑一个搜索即可。

接下来考虑使用dfs求解。

搜索的意义很简单，就是在 [a,b] 内，是 k 的倍数的数的个数。

对于每个 k，答案显然为 \lfloor b/k \rfloor -\lceil a/k \rceil +1。

但搜索的复杂度奇高无比，故考虑剪枝。

剪枝的过程也十分好理解，即当 x>b（x 意同上方）时可以停止搜索；此外，可以将原序列进行从大到小排序，使 x 尽快大于 b 。

此时的代码依旧错误，原因是我们算重了很多（譬如 6 在算 2 和 3 的时候都算了），考虑容斥。

令 f_x 指在题目区间内 x 的倍数个数，则 Ans=f_a+f_b+f_c...-f_{\rm{lcm}(a,b)}-f_{\rm {lcm}(a,c)}-f_{\rm{ lcm}(b,c)}...+f_{\rm {lcm}(a,b,c)}+...

Code

#include <iostream>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;

const int N=1e6+9;
int a,b,ans;
int l[N],tot,luc[N],len;
bool mark[N];
void dfs(int sta){
    if(sta>b)return;
    if(sta)l[++tot]=sta;
    bfs(sta*10+6);
    bfs(sta*10+8);
}
bool cmp(int a,int b){return a>b;}
__int128 gcd(__int128 a,__int128 b){
    if(!b)return a;
    else return gcd(b,a%b);
}
__int128 lcm(__int128 a,__int128 b){
    if(!a)return b;
    return a/gcd(a,b)*b;
}
void dfs_(int t,int num,__int128 lsm){
    if(lsm>b)return;
    if(t>len){
        if(!lsm)return;
        int jud=(num%2)?1:-1;
        ans+=jud*(floor(1.0*b/lsm)-ceil(1.0*a/lsm)+1);
        return;
    }   
    dfs_(t+1,num+1,lcm(lsm,luc[t]));
    dfs_(t+1,num,lsm);
}

signed main(){
    scanf("%lld%lld",&a,&b);
    dfs(0);
    for(int i=1;i<=tot;i++){
        if(!mark[i])luc[++len]=l[i];
        for(int j=i+1;j<=tot;j++)
            if(!(l[j]%l[i]))mark[j]=true;
    }//筛去已经是倍数的幸运数字
    sort(luc+1,luc+1+len,cmp);
    dfs_(1,0,0);
    printf("%lld",ans);
    return 0;
}