zcmimi's blog
查看原题

点击跳转

先预处理出所有幸运数字

当前要求的是[l,r]中的幸运数字

我们可以使用容斥,用[1,r]-[1,l-1]

假设当前幸运数字为x,[l,r]中是x的倍数的有\left \lfloor \frac rx \right \rfloor - \left \lfloor \frac lx \right \rfloor +1

[1,r],[1,l-1]中的幸运数字的倍数可能有交集

继续容斥:

选1个-选2个的lcm+选3个的lcm-...

剪枝:

  1. 可以发现,一个数是另一个合法倍数的倍数,那么这个数字相当于没用(因为被前面的统计过了),可以删掉

  2. 如果将幸运数字从大到小排序,搜索时可以更快突破边界

  3. 现在因为所有数都不满足是另外一个数的倍数,所以合并任意两个数的时候,lcm的最小情况就是乘上一个3

    所以对于所有>r/3的合法数字,显然不能够和任何一个数合并了,所以这一部分可以拿出来直接提前算好

剩下的直接暴搜

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100011
int tot=0,t=0;
ll ans=0,l,r,a[N];
bool v[N];
inline void init(){
    int h=0;
    while(h<=tot){
        ll x=a[h++]*10;
        if(x+6<=r)a[++tot]=x+6;
        if(x+8<=r)a[++tot]=x+8;
    }
}
const int mod=1000000007;
inline bool chk(ll a,ll b){
    int A=a/mod,B=b/mod;
    if(A*B)return 1;
    return a*b>r;
}
void calc(int x,ll s,int k){
    if(x>tot){
        if(s!=1){
            if(k&1)ans+=r/s-l/s;
            else ans-=r/s-l/s;
        }
        return;
    }
    calc(x+1,s,k);
    ll d=a[x]/__gcd(s,a[x]);
    if(!chk(s,d))calc(x+1,s*d,k+1);
}
inline void work(){
    sort(a+1,a+tot+1);
    for(int i=1;i<=tot;++i)
        for(int j=1;j<i;++j)
        if(a[i]%a[j]==0){v[i]=1;break;}

    for(int i=1;i<=tot;++i)
    if(!v[i]){
        if(a[i]<=r/3)a[++t]=a[i];
        else ans+=r/a[i]-l/a[i];
    }
    tot=t;
    reverse(a+1,a+tot+1);
    calc(1,1,0);
    printf("%lld\n",ans);
}
int main(){
    cin>>l>>r;
    --l;
    init();//找出所有"幸运号码"
    work();
}
LG 2567 [SCOI2010]幸运数字
comment评论
Search
search