CF55D Beautiful numbers

题意

\(t(\le 10)\)次询问区间\([l,r](1\le l\le r\le 9\times 10^{18})\)中能被每一位上数整除的数的个数，0算可以整除任何数。

最开始写了个假做法，既没算0复杂度也是假的

最开始把每个模数都压进去了，后来发现只压2520就可以了

然后前两位压前\(i\)位与\(\bmod 2520\)的结果，第三位最开始压了每个数字出现集合，这样就很屑。

可以直接压数字集合的最小公倍数，仅有不到50个取值，做一个Hash存一下就可以了。

写起来也简单

Code:

#include <cstdio>

#include <cstring>

#define ll long long

const int p=2520;

ll dp[20][p][50];

int yuy[p],bit[20],po[20],cnt;

int gcd(int x,int y){return y?gcd(y,x%y):x;}

int LCM(int x,int y){return y?x*y/gcd(x,y):x;}

ll dfs(int pos,int res,int lcm,int lim)

{

    if(!pos) return res%lcm==0;

    if(!lim&&~dp[pos][res][yuy[lcm]]) return dp[pos][res][yuy[lcm]];

    ll ret=0;

    for(int i=0,up=lim?bit[pos]:9;i<=up;i++)

        ret+=dfs(pos-1,(res+po[pos-1]*i)%p,LCM(lcm,i),lim&&i==up);

    return lim?ret:dp[pos][res][yuy[lcm]]=ret;

}

ll cal(ll x)

{

    int len=0;while(x) bit[++len]=x%10,x/=10;

    return dfs(len,0,1,1);

}

int main()

{

	memset(dp,-1,sizeof dp);

	int T;scanf("%d",&T);

	for(int i=1;i<p;i++)

        if(p%i==0)

            yuy[i]=++cnt;

    po[0]=1;for(int i=1;i<=18;i++) po[i]=po[i-1]*10%p;

	while(T--)

	{

		ll l,r;scanf("%lld%lld",&l,&r);

        printf("%lld\n",cal(r)-cal(l-1));

	}

	return 0;

}

2019.2.10

巴特西

洛谷 CF55D Beautiful numbers 解题报告

CF55D Beautiful numbers

题意

最新文章

热门文章