[洛谷P2567] SCOI2010 幸运数字

2024-03-02 18:58:04

问题描述

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

现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

输入格式

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

输出格式

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

样例输入输出

样例输入

1 10

样例输出

数据范围

对于30%的数据，保证1<=a<=b<=1000000

对于100%的数据，保证1<=a<=b<=10000000000

出处

四川省选2010

题目大意

定义集合\(S\)为包含所有\([1,10^{10}]\)中仅由6和8构成的数字的倍数集合。求区\([l,r]\)中属于\(S\)的元素个数。

解析

First of all

想到用类似于数位DP的方法，对每一位枚举选择哪个数，然后对每个构造出来的在区间\([l,r]\)数验证是否是一个幸运数字的倍数。显然，这种做法的复杂度极其之高，我们可以换一种思路。

另一个思路

既然难以验证一个数是不是幸运数字的倍数，那么我们反过来，提前构造出所有幸运数字(具体可用搜索实现)，然后枚举他们的倍数，统计有多少个是在\([l,r]\)中，得到答案。

如何统计呢？

引理

对于一个数\(x\),它在区间\([l,r]\)的倍数个数为
\[ \left \lfloor \frac{r}{x} \right \rfloor - \left \lceil \frac{l}{x} \right \rceil+1 \]

所以，是不是对每一个幸运数字代入公式计算一下，累加答案就可以了呢？

容斥

答案是否定的。

一个很简单的道理，48是6和8的倍数，所以它会同时被6和8计算，也就是说，48被重复统计了一次。总结一下，任意几个幸运数字的\(lcm\)都会被重复统计。

拓展：\(lcm\)

\(lcm(a,b)\)指的是\(a\)和\(b\)的最小公倍数。计算公式为\(lcm(a,b)=a*b/gcd(a,b)\)

~~如果gcd也不知道就自行百度吧。~~

既然会重复统计\(lcm\)，我们就减掉一份两两最小公倍数带来的贡献。但是这样又会重复减掉任意三个数的最小公倍数的贡献，那么我们再加回来，又多加了任意四个数最小公倍数的贡献......。公式化之后就是
\[ ans=\sum_{i}f(a[i])-\sum_{i,j}f(lcm(a[i],a[j]))+\sum_{i,j,k}f(lcm(a[i],a[j],a[k]))-...... \]
其中\(f(x)=\left \lfloor \frac{r}{x} \right \rfloor - \left \lceil \frac{l}{x} \right \rceil+1\)，\(a[i]\)为第i个幸运数字。

搜索

有了容斥式，我们来考虑如何计算。用DFS可以很方便的解决。每次枚举一个数是否被选，最后如果选的数个数为奇数就加上\(f(lcm)\)，否则减掉。

但这样还是不能通过。

剪枝

考虑类似于6和66的关系，66是6的倍数，那么66的倍数也都会被6计算到。所以，我们可以删去所有是其他幸运数字倍数的幸运数字。
如果当前\(lcm\)已经大于\(r\)，那么显然没有什么枚举下去的必要了。这时就可以剪枝。
可以把所有剩下的幸运数字从大到小排序后再DFS。这样在前几个阶段中就删去了很多\(lcm\)大于\(r\)的情况。

一个小问题

即便如此，这道题提交时还是会T几个点。原因是在计算DFS过程中计算\(lcm\)时\(long\ \ long\)溢出了。因此，我们需要使用\(long \ \ double\)类型计算避免此问题。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int lim=10000000000;
int i,j,l,r,num[1000002],cnt,n,ans;
bool vis[1000002];
void make(int x,int now)
{
    if(now>lim) return;
    if(now!=0) num[++cnt]=now;
    make(x+1,now*10+6);
    make(x+1,now*10+8);
}
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
void dfs(int x,int cnt,int lcm)
{
    if(x==n+1){
        if(lcm!=1) ans+=(cnt%2==0?-1:1)*(r/lcm-(l/lcm+(l%lcm==0?0:1))+1);
        return;
    }
    dfs(x+1,cnt,lcm);
    long double tmp=1.0*lcm/gcd(lcm,num[x])*num[x];
    if(tmp>r) return;
    dfs(x+1,cnt+1,tmp);
}
int my_comp(const int &x,const int &y)
{
    return x>y;
}
signed main()
{
    cin>>l>>r;
    make(0,0);
    sort(num+1,num+cnt+1);
    for(i=1;i<=cnt;i++){
        for(j=i+1;j<=cnt;j++){
            if(num[j]%num[i]==0) vis[j]=1;
        }
    }
    for(i=1;i<=cnt;i++){
        if(!vis[i]) num[++n]=num[i];
    }
    sort(num+1,num+n+1,my_comp);
    dfs(1,0,1);
    printf("%lld\n",ans);
    return 0;
}

码农公寓