首页 > 代码库 > [bzoj1853][Scoi2010][幸运数字] (容斥原理)

[bzoj1853][Scoi2010][幸运数字] (容斥原理)

2024-09-02 16:33:16   215人阅读

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

Solution

#include <stdio.h>#include <algorithm>#define N 10010#define L long longtemplate < class T > void EC(T &a , T &b){    T t=a;    a=b;    b=t;}template < class T > T GD(T a , T b){    return b ? GD(b , a % b) : a;}int _t,_n;bool V[N];L l , r , A[N] , ans;void PR(int x , L y){    if(y > r)        return;    if(x)        A[++_t] = y;    PR(x + 1 , y * 10 + 6);    PR(x + 1 , y * 10 + 8);}void DF(int x , int y , L z){    if(x > _n)        {        if(y)            ans += y & 1 ? r / z - (l - 1) / z : (l - 1) / z - r / z;        return;        }    DF(x + 1 , y , z);    L t = z / GD(z , A[x]);    if(((double)A[x] * t) <= r)        DF(x + 1 , y + 1 , A[x] * t);}int main(){    scanf("%lld%lld" , &l , &r);    PR(0 , 0);    std::sort(A + 1 , A + _t + 1);    for(int i = 1;i <= _t;i++)        if(!V[i])            {            A[++_n]=A[i];            for(int j = i + 1;j <= _t;j++)                if(A[j] % A[i] == 0)                    V[j]=1;            }    for(int i = 1;i + i <= _n;i++)        EC(A[i],A[_n-i+1]);    DF(1 , 0 , 1);    printf("%lld\n",ans);    return 0;}

 

[bzoj1853][Scoi2010][幸运数字] (容斥原理)


联系
我们