【每日一题】3月23日[SCOI2010]幸运数字

题意

我们称含6和8的号码是“幸运号码”凡是幸运号码的倍数都称为“近似幸运号码”

求一个区间里的“近似幸运号码”个数

直接暴力找到所有的“幸运号码”然后其他的数就一定是这些数的倍数 我们从小到大sort一下 然后找这些数的倍数

然后对这些数进行容斥 统计答案即可

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
const int N = (1 << 11) + 7;
const int INF = 0x3f3f3f3f;

struct node{
    ll val;
    int id;
};
bool cmp(node a , node b){
    return a.val < b.val;
}
ll n , m ;
ll tot , a[N] , cnt , flag[N];

void dfs(ll x){
    if(x > m)    return ;
    a[++tot] = x;
    dfs(x * 10 + 6);
    dfs(x * 10 + 8);
}

ll ans = 0;

void dfs1(int dep , int sz , ll now){
    if(now > m)    return ;
    if(dep == cnt + 1){
        ll tmp = m / now - (n - 1) / now;
        if(sz & 1)    ans += tmp;
        else ans -= tmp;
        return ;
    }
    if(m >= 1.0 * now / gcd(now , a[dep]) * a[dep])
        dfs1(dep + 1 , sz + 1 , now / gcd(now , a[dep] )* a[dep]);
    dfs1(dep + 1 , sz , now);
}

void solve(){
    n = read() , m = read();
    dfs(6) , dfs(8);
    for(int i = 1 ; i <= tot ; ++i){
        for(int j = 1 ; j <= tot ; ++j){
            if(a[i] > a[j] && a[i] % a[j] == 0)
                flag[i] = 0;
        }
    }
    for(int i = 1 ; i <= tot ; ++i){
        if(!flag[i])    a[++cnt] = a[i];
    }
    sort(a + 1 , a + cnt + 1 , greater<ll>());
    for(int i = 1 ; i <= cnt ; ++i)
        dfs1(i + 1 , 1 , a[i]);
    cout<<ans<<endl;
}

int main(void){
    solve();

    return 0;
}