BZOJ 1853 - [Scoi2010]幸运数字

#容斥原理 #DFS #剪枝
Published on 2016-06-12

题目地址

描述

定义幸运数字是其十进制表示中只含有 6, 8 的数，求 [l,r](l≤r≤1010)[l, r](l \le r \le 10^{10}) 内能被幸运数字整除的数。

分析

我们考虑极限情况，估算一下规模：l=1,r=1010l = 1, r = 10^{10}。
这样总共有 21+22+⋯+210=211−2=20462^1 + 2^2 + \cdots + 2^{10} = 2^{11} - 2 = 2046 个幸运数字。显然，如果一个幸运数字能被另外一个幸运数字整除，那么这个幸运数字就无用。去掉这种情况后有 943943 个数。
根据容斥原理，能被 A,BA, B 中任意一个整除的数的个数为 能被 AA 整除的数 + 能被 BB 整除的数 - 能被 LCM(A,B)\mathrm{LCM}(A, B) 整除的数。
而我们在这里有 943 个数，有 29432^{943} 种数，是不是不能用容斥原理呢？

可以用。因为只要 LCM 超过了 rr，后面完全可以不考虑，那么我们可以将数从大到小排序，用 DFS 来计算容斥，一旦大于 rr 就立刻剪枝。这样时间是可以承受的。
为什么不能从小到大排序，实际有用的乘积不是一样的吗？对，虽然是一样的，但是我们的剪枝次数却变多了，导致会慢很多。

Trick：计算 LCM 判断大于 rr 的时候有可能爆 LL，所以可以转换成 double 计算。

代码

//  Created by Sengxian on 6/12/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1853 容斥原理 + DFS 剪枝
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<ll> a, b;
vector<bool> flag;
ll l, r, ans = 0;

ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}

void dfs(int k, int sign, ll lcm) {
    if (k == (int)b.size()) {
        if (lcm > 1) ans += sign * (r / lcm - (l - 1) / lcm);
        return;
    }
    dfs(k + 1, sign, lcm);
    ll tmp = b[k] / gcd(b[k], lcm);
    if ((long double)tmp * lcm > r) return; //从大往小选择，这样就可以很快超过 r，被剪枝。
    dfs(k + 1, -sign, lcm * tmp);
}

ll solve() {
    queue<ll> q;
    q.push(6LL), q.push(8LL);
    while (!q.empty()) {
        ll now = q.front(); q.pop();
        a.push_back(now);
        if (now * 10 + 6 <= r) q.push(now * 10 + 6);
        if (now * 10 + 8 <= r) q.push(now * 10 + 8);
    }
    sort(a.begin(), a.end());
    flag = vector<bool>(a.size());
    for (int i = 0; i < (int)a.size(); ++i)
        for (int j = i + 1; j < (int)a.size(); ++j)
            if (a[j] % a[i] == 0) flag[j] = true;
    for (int i = 0; i < (int)a.size(); ++i) if (!flag[i]) b.push_back(a[i]);
    reverse(b.begin(), b.end());
    ans = 0;
    dfs(0, -1, 1);
    return ans;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    scanf("%lld%lld", &l, &r);
    printf("%lld\n", solve());
    return 0;
}
BZOJ 3198 - [Sdoi2013]spring