2393Cirno的完美算数教室容斥

2022-08-13 15:53:00

2393: Cirno的完美算数教室

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 652 Solved: 389
[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

简单容斥
找出区间内所有2和9构成的数,筛出他们的倍数，用ans+-

~~和scoi2010一模一样的题目啊。http://www.cnblogs.com/wsy01/p/8023992.html~~

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

#define N 5000

using namespace std;

ll a,b,c[N],d[N],ans;int vis[N],cnt,tot;

void predfs(int pos,ll val){

    if(!pos){

        if(val<=b)

        c[++cnt]=val;

        return;

    }

    predfs(pos-1,val*10+2);

    predfs(pos-1,val*10+9);

}

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

ll gcd(ll a,ll b){

    if(!b)return a;

    return gcd(b,a%b);

}

void dfs(int u,ll val,int ok){

    if(u>tot){

        if(ok&1)ans+=b/val-(a-1)/val;

        else if(ok)ans-=b/val-(a-1)/val;

        return;

    }

    dfs(u+1,val,ok);

    ll g=gcd(val,d[u]);

    ll lcm=val/g*d[u];

    if(lcm<0||lcm>b)return;

    dfs(u+1,lcm,ok+1);

}

int main(){

    cin>>a>>b;

    for(int i=1;i<=10;i++)

    predfs(i,0);

    for(int i=1;i<=cnt;i++){

        if(vis[i])continue;

        int fg=0;d[++tot]=c[i];

        for(int j=i+1;j<=cnt;j++)

        if(c[j]%c[i]==0)vis[j]=1;

    }

    sort(d+1,d+1+tot,cmp);

    dfs(1,1,0);

    cout<<ans;

    return 0;

}