【BZOJ-1853&2393】幸运数字&Cirno的完美算数教室 容斥原理 + 爆搜 + 剪枝

时间：2023-05-02 19:21:26

1853: [Scoi2010]幸运数字

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 1817  Solved: 665
[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

Source

2393: Cirno的完美算数教室

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 299  Solved: 183
[Submit][Status][Discuss]

Description

~Cirno发现了一种baka数，这种数呢~只含有2和⑨两种数字~~现在Cirno想知道~一个区间中~~有多少个数能被baka数整除~但是Cirno这么天才的妖精才不屑去数啦只能依靠聪明的你咯。

Input

一行正整数L R
( 1 < L < R < 10^10)

Output

一个正整数，代表所求的答案

Sample Input

1 100

Sample Output

58

HINT

Source

Solution

容斥原理 爆搜 剪枝

先预处理出baka数(幸运数),再去一下重(删除能被其他baka数整除的)

容斥之前有一个结论:

N内a或b的倍数的个数=N/a+N/b-N/lcm(a,b),即:a在N以内的倍数+b在N以内的倍数-a和b两个在N以内的相同的倍数(所以从 最小公倍数 开始)

然后就可以容斥,爆搜+剪枝 就可以A了 一个最行之有效的剪枝就是一开始所说的去重 也可以吧超过R的部分直接忽略

By The Way:baka数可以正常A,幸运数那题,需要改成unsigned long long,不然会TLE (可是本机明明跑的一样快)

Code

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 100100

unsigned long long L,R;

int top,Top;

unsigned long long stack[maxn],ans;

void Prework(long long x)

{

    if (x<=R) stack[++top]=x; else return;

    Prework(x*+); Prework(x*+);

}

bool cmp(long long a,long long b) {return a>b;}

long long gcd(long long a,long long b) {if (!b) return a; return gcd(b,a%b);}

void DFS(int dep,int t,long long x)

{

    if (dep==Top+)

        {

            if (t%) ans+=R/x-(L-)/x;

                else if (t) ans-=R/x-(L-)/x;

            return;

        }

    DFS(dep+,t,x);

    if (stack[dep]*x/gcd(stack[dep],x)<=R)

        DFS(dep+,t+,stack[dep]*x/gcd(stack[dep],x));

}

int main()

{

//    freopen("a.in","r",stdin);

//    freopen("a.out","w",stdout);

    scanf("%lld%lld",&L,&R);

    Prework(); Prework();

    sort(stack+,stack+top+);

//    for (int i=1; i<=top; i++) printf("%d ",stack[i]); puts("");

    for (int i=; i<=top; i++)

        if (stack[i])

            {

                for (int j=i+; j<=top; j++)

                    if (stack[j]%stack[i]==) stack[j]=;

                stack[++Top]=stack[i];

            }

    sort(stack+,stack+Top+,cmp);

//    for (int i=1; i<=Top; i++) printf("%d ",stack[i]); puts("");

    DFS(,,);

    printf("%lld\n",ans);

    return ;

}

BZOJ1853

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 10010

int L,R,top,Top;

long long stack[maxn],ans;

void Prework(long long x)

{

    if (x<=R) stack[++top]=x; else return;

    Prework(x*+); Prework(x*+);

}

bool cmp(long long a,long long b) {return a>b;}

long long gcd(long long a,long long b) {if (!b) return a; return gcd(b,a%b);}

void DFS(int dep,int t,long long x)

{

    if (dep==Top+)

        {

            if (t%) ans+=R/x-(L-)/x;

                else if (t) ans-=R/x-(L-)/x;

            return;

        }

    DFS(dep+,t,x);

    if (stack[dep]*x/gcd(stack[dep],x)<=(long long)R)

        DFS(dep+,t+,stack[dep]*x/gcd(stack[dep],x));

}

int main()

{

    scanf("%d%d",&L,&R);

    Prework(); Prework();

    sort(stack+,stack+top+);

//    for (int i=1; i<=top; i++) printf("%d ",stack[i]); puts("");

    for (int i=; i<=top; i++)

        if (stack[i])

            {

                for (int j=i+; j<=top; j++)

                    if (stack[j]%stack[i]==) stack[j]=;

                stack[++Top]=stack[i];

            }

    sort(stack+,stack+Top+,cmp);

//    for (int i=1; i<=Top; i++) printf("%d ",stack[i]); puts("");

    DFS(,,);

    printf("%lld\n",ans);

    return ;

}

去CodeVS群问了波..感觉弱智+10

相关文章