【做题笔记】bzoj2393

题目大意

定义一种数字只含有$2$和$9$,求出一个范围内能被这种数字整除的数字个数

解题过程

思路

利用容斥原理先把范围内只含有$2$和$9$的数字筛出来,然后暴力枚举求出合法数字个数,注意需要剪枝

代码

#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
#define gcd(a,b) __gcd(a,b)

const int MAXN = 2e3 + 5;

int t, vis[MAXN];
ll n, m, a[MAXN], b[MAXN], ans = 0, l, r;

void Pre(ll x, ll y) {
    if (y > r) return;
    if (x > 1) a[++m] = y;
    if (x > t) return;
    Pre(x + 1, y * 10 + 2);
    Pre(x + 1, y * 10 + 9);
}

void Dfs(ll x, ll y, ll z) {
    if (x > n) {
        if (y % 2 == 1) ans += r / z - (l - 1) / z;
        else if (y)
            ans -= r / z - (l - 1) / z;
        return;
    }
    Dfs(x + 1, y, z);
    ll nxt = a[x] * z / gcd(a[x], z);
    if (nxt <= r)
        Dfs(x + 1, y + 1, nxt);
    return;
}

int main() {
    cin >> l >> r;
    t = (int)(log(r * 1.0) / log(10)) + 1;
    Pre(1, 0);
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= m; i++)
        if (!vis[i]) {
            b[++n] = a[i];
            for (int j = i + 1; j <= m; j++)
                if (!a[j] % a[i])
                    vis[j] = 1;
        }
    for (int i = 1; i <= n; i++)
        a[n - i + 1] = b[i];
    Dfs(1, 0, 1);
    cout << ans << endl;
    return 0;
}