【题解】bzoj1853

题目大意

定义幸运数字为只含有$6$和$8$的数字,求出一个范围内幸运数字倍数的个数

解题过程

解题思路

先利用容斥预处理出幸运数字,然后暴力枚举合法数字的个数,注意剪枝

代码

#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;

const int MAXN = 1e5 + 5;

ll l, r, a[MAXN], ans, b[MAXN];
int tot, n;
bool vis[MAXN];

#define gcd(a,b) __gcd(a,b)

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

void Dfs(int x, int now, ll val) {
    if (x == n + 1) {
        if (now == 0 || val == 0) return;
        if (now % 2 == 1) ans += r / val - (l - 1) / val;
        else ans -= r / val - (l - 1) / val;
        return;
    }
    Dfs(x + 1, now, val);
    ll tmp;
    if (now == 0) {
        Dfs(x + 1, now + 1, b[x]);
        return;
    }
    tmp = val / gcd(val, b[x]);
    if ((double)b[x] * tmp > r) return;
    Dfs(x + 1, now + 1, b[x] * tmp);
}

int main() {
    cin >> l >> r;
    Pre(0);
    sort(a + 1, a + tot + 1);
    for (int i = 1; i <= tot; i++) if (!vis[i]) {
            b[++n] = a[i];
            for (int j = i + 1; j <= tot; j++)
                if (a[j] % a[i] == 0) vis[j] = true;
        }
    for (int i = 1; i <= n / 2; i++) swap(b[i], b[n - i + 1]);
    Dfs(1, 0, 0);
    cout << ans << endl;
    return 0;
}