题目描述

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

题目分析

思路还是很简单的啦
先预处理出区间只有6 8组成的数字 然后容斥原理一波就好了
简单的学习了一下容斥原理

code:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
long long l,r,sta[5010];
void init(long long x)
{
    if(x>r) return ;
    sta[++sta[0]]=x;
    init(x*10+6),init(x*10+8);
}
long long ans;
long long gcd(long long x,long long y)
{ return !y?x:gcd(y,x%y); }
int n;
void dfs(int id,long double sum,int deep)
{
    if(sum>r) return ;
    long long nm=sum;
    if(deep&1) ans+=(r/nm-(l-1)/nm);
    else ans-=(r/nm-(l-1)/nm);
    for(int i=id+1;i<=n;i++)
    {
        long double tmp=sum/gcd(nm,sta[i]);
        if(tmp>r) continue;
        dfs(i,tmp*sta[i],deep+1);
    }
}
int cmp(long long x,long long y) { return x>y; }
int main()
{
    scanf("%lld%lld",&l,&r);
    init(0);
    for(int i=1;i<=sta[0];i++)
        for(int j=1;j<=sta[0];j++)
            if(i!=j&&sta[j]&&sta[i]%sta[j]==0) sta[i]=0;
    sort(sta+1,sta+sta[0]+1,cmp);
    for(;sta[n+1];n++);
    dfs(0,1,1);
    printf("%lld",r-(l-1)-ans);
}

code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
long long l,r,sta[5010];
void init(long long x)
{
    if(x>r) return ;
    sta[++sta[0]]=x;
    init(x*10+2),init(x*10+9);
}
long long ans;
long long gcd(long long x,long long y)
{ return !y?x:gcd(y,x%y); }
int n;
void dfs(int id,long double sum,int deep)
{
    if(sum>r) return ;
    long long nm=sum;
    if(deep&1) ans+=(r/nm-(l-1)/nm);
    else ans-=(r/nm-(l-1)/nm);
    for(int i=id+1;i<=n;i++)
    {
        long double tmp=sum/gcd(nm,sta[i]);
        if(tmp>r) continue;
        dfs(i,tmp*sta[i],deep+1);
    }
}
int cmp(long long x,long long y) { return x>y; }
int main()
{
    scanf("%lld%lld",&l,&r);
    init(0);
    for(int i=1;i<=sta[0];i++)
        for(int j=1;j<=sta[0];j++)
            if(i!=j&&sta[j]&&sta[i]%sta[j]==0) sta[i]=0;
    sort(sta+1,sta+sta[0]+1,cmp);
    for(;sta[n+1];n++);
    dfs(0,1,1);
    printf("%lld",r-(l-1)-ans);
}