BZOJ 1853 幸运数字(容斥原理+dfs)

题意:求闭区间内能被6和8组成的数字整除的数目。n<=1e11.

我们可以预处理出这些6和8组成的数字，大概2500个，然后排除一些如88，66的情况。这样大概还剩下1000个。

转化为[0,r]和[0,l-1]的问题，显然需要运用容斥原理。ans=n/6+n/8+n/68+...+...-n/lcm(6,8)-n/lcm(6,68)......

因此用dfs即可计算出来，这样一看复杂度好像是2^1000的样子，但是注意到lcm增长的很快，如果lcm>n那么显然之后的这些情况就可以忽略了。

这就是一个强有力的剪枝。

另外从大到小dfs要比从小到大dfs要好。大概常数小？

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi acos(-1.0)

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

LL num[], pos1, pos2, p[], mark[];

void init(){

    p[]=; FOR(i,,) p[i]=p[i-]*;

    int l=, r=, tmpl, tmpr;

    num[++pos1]=; num[++pos1]=;

    FOR(i,,) {

        tmpl=r+;

        FOR(j,l,r) num[++pos1]=*p[i-]+num[j];

        FOR(j,l,r) num[++pos1]=*p[i-]+num[j];

        tmpr=pos1;

        l=tmpl; r=tmpr;

    }

    FOR(i,,pos1) {

        int flag=true;

        FO(j,,i) if (num[i]%num[j]==) {flag=false; break;}

        if (flag) mark[++pos2]=num[i];

    }

    mark[++pos2]=1e16;

}

LL dfs(int pos, int flag, LL x, LL cheng){

    if (pos<=) return ;

    LL res=;

    res+=dfs(pos-,flag,x,cheng);

    LL tmp=__gcd(cheng,mark[pos]);

    if (cheng/tmp<=(double)x/mark[pos]) {

        LL tt=cheng/tmp*mark[pos];

        res+=dfs(pos-,flag^,x,tt);

        res+=(flag?x/tt:-x/tt);

    }

    return res;

}

LL sol(LL x){

    for (int i=pos2; i>=; --i) if (mark[i]<=x) return dfs(i,,x,);

    return ;

}

int main ()

{

    init();

    LL a, b;

    scanf("%lld%lld",&a,&b);

    printf("%lld\n",sol(b)-sol(a-));

    return ;

}

巴特西

BZOJ 1853 幸运数字(容斥原理+dfs)

最新文章

热门文章