[原创]BZOJ1853 [Scoi2010]幸运数字 [容斥原理]【组合数学】

2017-02-13 22:15:06 Tabris_ 阅读数：634

博客爬取于2020-06-14 22:41:35
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/55058123

题目连接：https://vjudge.net/problem/HYSBZ-1853
------------------------------------------------------------------------------------------------------------.
1853: [Scoi2010]幸运数字

Time Limit: 2 Sec Memory Limit: 64 MB
Submit: 2284 Solved: 834
[Submit][Status][Discuss]
Description

在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。 现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。
Input

输入数据是一行，包括2个数字a和b
Output

输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数
Sample Input

【样例输入1】

1 10

【样例输入2】

1234 4321

Sample Output

【样例输出1】

2

【样例输出2】

809

HINT

【数据范围】
对于30%的数据，保证1 < =a < =b < =1000000
对于100%的数据，保证1 < =a < =b < =10000000000

------------------------------------------------------------------------------------------------------------.

首处理出所有的幸运数字,
只有2102^{10}个.
然后找到这些数中的"幸运素数"(就是这些数组成的序列中不能被其他元素整除的数~~(类似线性基?!)~~)

找到这些数,那么 其实就把这个问题就是成求[a,b]内那些"幸运素数"的倍数有多少个就好了.

答案就是calc(b)−calc(a−1)calc(b)-calc(a-1)

很明显的一个容斥原理,
calc(x)=ans=[x一个幸运素数的积]−[x两个幸运素数的积]+[x三个幸运素数的积]−....calc(x) = ans = \left[\dfrac{x}{一个幸运素数的积}\right] - \left[\dfrac{x}{两个幸运素数的积}\right] + \left[\dfrac{x}{三个幸运素数的积}\right] -....

上述问题很容易 不再赘述

附本题代码
------------------------------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
LL l,r,a[10000],cnt,ans;
vector<LL>b;
void dfs1(LL x,int bit){
    if(bit>10) return ;
    if(x) a[++cnt] = x;
    dfs1(x*10+6,bit+1);
    dfs1(x*10+8,bit+1);
}

void init(){
    cnt=0,dfs1(0,0); //printf("%I64d\n",cnt);
    sort(a+1,a+cnt+1);
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<i;j++){
            if(a[j]&&a[i]%a[j]==0){
                a[i]=0;break;
            }
        }
        if(a[i])b.pb(a[i]);
    }
}

LL dfs2(int pos,bool flag ,LL val,LL &x){
    if(pos<0) return 0;
    LL ans = 0;
    ans+=dfs2(pos-1,flag,val,x);
    LL g = _gcd(val,b[pos]);
    if(val/g <= x/b[pos]){
        g = val/g*b[pos];
        if(flag) ans += x/g;
        else     ans -= x/g;
        ans+=dfs2(pos-1,!flag,g,x);
    }
    return ans;
}

LL calc(LL x){
    ans = 0;
    int id = 0,sz=b.size();
    while(id<sz && b[id]<=x) id++;
    return dfs2(id-1,true,1ll,x);
}
void work(){
    cin>>l>>r;
    cout<<calc(r)-calc(l-1)<<endl;
}

int main(){
    init();
    work();
    return 0;
}