首页 > 代码库 > BZOJ1853_幸运数字

BZOJ1853_幸运数字

2024-07-12 15:54:59   220人阅读

如果一个数字仅由6或者8构成，那么这个数字是幸运数字；如果一个数字是幸运数字的倍数，那么就是近似的幸运数。

给定区间，求有多少个近似幸运数字位于这个区间之内。

典型的容斥原理。

首先，弄出所有的幸运数字，把那些本来就是另外幸运数字的倍数的幸运数字去掉（因为它肯定可以通过前面小的数字统计到）

f[n]=sigama( n/a1+n/a2+....-n/lcm(ai,aj)...+n/lcm(ai,aj,ak)....... )

这已经很明显了。

不过注意统计的时候也有一些技巧可言。首先对于一个数字，我们判断它对应的最大的a[]是那个。然后从那个数开始往前拼凑，一遍拼凑一遍统计答案即可。

因为大数lcm很容易就超过了n的大小，可以及时剪掉。

注意，中间gcd会爆longlong，所以lcm的时候稍微注意一下。

 

 

召唤代码君;

 

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>typedef long long ll;using namespace std;const ll lim=10000000000LL;ll f[200020],n=0,N;void init(ll x){    if (x>lim) return ;    if (x) f[++n]=x;    init(x*10+6),init(x*10+8);}ll gcd(ll A,ll B){    return B==0?A:gcd(B,A%B);}void _init(){    init(0);    sort(f+1,f+1+n);    for (int i=1; i<=n; i++)        for (int j=1; j<i; j++)            if (f[j] && f[i]%f[j]==0)             {                f[i]=0;                break;            }    N=0;    for (int i=1; i<=n; i++)        if (f[i]) f[++N]=f[i];    n=N;}ll dfs1(ll pos,bool flag,ll sum,ll x){    if (pos<=0) return 0;    ll ans=0;    ans+=dfs1(pos-1,flag,sum,x);    ll g=gcd(sum,f[pos]);    if (sum/g <= x/f[pos])    {        g=sum/g*f[pos];        if (flag) ans-=x/g;            else ans+=x/g;        ans+=dfs1(pos-1,!flag,g,x);    }    return ans;}ll count(ll x){    int pos=1;    while (pos<=n && f[pos]<=x) pos++;    ll ans=dfs1(pos-1,false,1,x);    return ans;}int main(){    _init();    ll A,B;    while (cin>>A>>B)        cout<<count(B)-count(A-1)<<endl;    return 0; }


联系
我们