SCOI2010 幸运数字

摘要

幸运数字:只包含数字 6 和 8 的那些号码。近似幸运数字:幸运数字的倍数。求 的近似幸运数字的个数。

.

首先想到的就是容斥,考虑预处理所有的近似幸运数字,直接容斥是自闭的。做一下剪枝

如果 ,直接退出;如果两个幸运数字 满足 ,那么 就是没有意义的,因此可以预处理直接筛掉;将剩下的按从大到小排序以更快到达边界

做了上述剪枝可以拿 70. 还有什么需要剪的吗?

每一次合并 lcm 的时侯,lcm 至少乘 2. 因此对于那些 的近似幸运数字 ,他们不可能和别的幸运数字做容斥,只能自己做贡献,于是直接算这些贡献,剩下的再来容斥即可。

#include <algorithm>
#include <cstdio>
#define int long long
using namespace std;
const int N = 1e5;
int a, b, ans;
int c[N], lc;

void dfs(int x) {// 处理所有幸运数字
    c[++lc] = x;
    if (x*10+6> b) return;
    dfs(x*10+6), dfs(x*10+8);
}
void sieve() {// 把倍数的幸运数字筛掉
    int tmp[N], lt = 0;
    for (int i = 1; i <= lc; i++) {
        for (int j = 1; j <= lt; j++) {if (c[i]%tmp[j]) continue;
            c[i] = 0;
            break;
        }
        if (c[i] > b/2) ans += b/c[i]-(a-1)/c[i], c[i] = 0;
        if (c[i]) tmp[++lt] = c[i];
    }
    for (int i = 1; i <= lt; i++) c[i] = tmp[i];
    lc = lt;
}
void prework() {
    dfs(0);
    sort(c+1, c+lc+1);
    sieve();
}
int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}
void dfs(int k, int last, int lcm) {
    if (k != 0) ans += (k%2*2-1)*(b/lcm-(a-1)/lcm);
    for (int i = last-1; i>0; i--) {  // 倒序
        int g = gcd(lcm, c[i]);
        g = lcm*c[i]/g;
        if (g <= b) dfs(k+1, i, g);
    }
}
signed main() {
    scanf("%lld%lld", &a, &b);
    prework();
    dfs(0, lc+1, 1);
    printf("%lld", ans);
    return 0;
}

  转载请注明: Sshwy's Blog SCOI2010 幸运数字

 上一篇
欧几里德算法专题 欧几里德算法专题
摘要 鉴于初等数论的内容太多,于是单独分出一个欧几里德算法的文章,主要讲欧几里德算法,扩欧和类欧 欧几里得算法即辗转相除法,基于 的原理,用于求解最大公约数的问题 int gcd(
2019.05.01
下一篇 
[Luogu3801] 红色的幻想乡 [Luogu3801] 红色的幻想乡
摘要 今天不是打题的好日子,以至于我和 90 分杠上了 一个 的方格地区,一开始没有任何一个地区被红雾遮盖。蕾米莉亚每次站在某一个地区上,向东南西北四个方向各发出一条无限长的红雾,可以影响到整行 / 整列,但不
2019.04.30
  目录