M_sea

洛谷2567 [SCOI2010]幸运数字
Luogu分析发现自己容斥太菜了,于是来刷几道容斥题。首先预处理出 $[1,b]$ 范围内的所有幸运号码。这个 d...
扫描右侧二维码阅读全文
01
2019/09

洛谷2567 [SCOI2010]幸运数字

Luogu

分析

发现自己容斥太菜了,于是来刷几道容斥题。

首先预处理出 $[1,b]$ 范围内的所有幸运号码。这个 dfs 一下就行了。

考虑到 $[a,b]$ 范围内 $x$ 的倍数个数为

$$ \Big\lfloor\frac{b}{x}\Big\rfloor-\Big\lceil\frac{a}{x}\Big\rceil+1 $$

然而两个不同的幸运号码的倍数可能是会重复的,于是可以容斥。

设 $f(i)$ 为 $[a,b]$ 内 $i$ 个幸运号码的 $\operatorname{lcm}$ 的倍数的个数,那么答案为 $f(1)-f(2)+f(3)-f(4)+\cdots$ 。

这个似乎只能搜出所有的情况做,于是我们考虑一些剪枝:

  • 如果一个幸运号码是另一个幸运号码的倍数,那么显然这个幸运号码是无用的,可以直接去掉。
  • 如果当前的 $\operatorname{lcm}$ 已经比 $b$ 大了,直接返回。
  • 把所有幸运号码从大到小排序,这样子 $\operatorname{lcm}$ 会更快超过 $b$ 。

这样子就能过了。

另外注意两个 $10^{10}$ 级别的数相乘是会爆 long long 的,需要开 double

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline ll cmp(ll a,ll b) { return a>b; }
inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

ll a,b,ans=0;
ll tmp[N]; int tmpcnt=0;
ll num[N]; int cnt=0;
int v[N];

inline void dfs(int p,ll w) {
    if (w>b||p>10) return;
    tmp[++tmpcnt]=w;
    dfs(p+1,w*10+6),dfs(p+1,w*10+8);
}

inline ll calc(ll w) {
    return (b/w)-(a/w+(a%w!=0))+1;
}

inline void solve(int p,int c,ll w) {
    if (p>cnt) {
        if (!c) return;
        ans+=calc(w)*((c&1)?1:-1);
        return;
    }
    solve(p+1,c,w);
    if (1.0*w/__gcd(w,num[p])*num[p]<=b) // 这里可能会爆 long long
        solve(p+1,c+1,w/__gcd(w,num[p])*num[p]);
}

int main() {
    a=read(),b=read();
    dfs(1,6),dfs(1,8);
    sort(tmp+1,tmp+tmpcnt+1);
    for (re int i=1;i<=tmpcnt;++i) {
        if (!v[i]) num[++cnt]=tmp[i];
        for (re int j=i+1;j<=tmpcnt;++j)
            if (tmp[j]%tmp[i]==0) v[j]=1;
    }
    sort(num+1,num+cnt+1,cmp);
    solve(1,0,1); printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 01 日 05 : 14 PM

发表评论