【CF55D】Beautiful numbers（动态规划）

题面

题解

数位\(dp\)

如果当前数能够被它所有数位整除，意味着它能够被所有数位的\(lcm\)整除。

所以\(dp\)的时候前面所有数的\(lcm\)要压进\(dp\)值中。

又因为\(lcm\)的余数也是有意义的，但是又不能暴力记，

所以记录一下\([1,9]\)所有数的\(lcm\)也就是\(2520\)就好了。

但是数组太大，实际上，有意义的\(lcm\)个数只有不到\(50\)个，重新编号就可以压缩状态了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

inline ll read()

{

    ll x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int lcm[3000],tot,p[50];

ll f[20][50][2520];

int W[20],top;

int LCM(int a,int b){if(b==0)return a;return a/__gcd(a,b)*b;}

ll dfs(int x,int Lcm,int r,int t)

{

	if(!x)return r%p[Lcm]==0;

	if(f[x][Lcm][r]!=-1&&!t)return f[x][Lcm][r];

	int up=t?W[x]:9;ll ret=0;

	for(int i=0;i<=up;++i)

		ret+=dfs(x-1,lcm[LCM(p[Lcm],i)],(r*10+i)%2520,t&(i==W[x]));

	if(!t)f[x][Lcm][r]=ret;

	return ret;

}

ll Solve(ll x)

{

	top=0;

	while(x)W[++top]=x%10,x/=10;

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

}

int main()

{

	for(int i=0;i<(1<<9);++i)

	{

		int sum=1;

		for(int j=0;j<9;++j)

			if(i&(1<<j))sum=LCM(sum,j+1);

		lcm[sum]=1;

	}

	for(int i=1;i<=2520;++i)if(lcm[i])lcm[i]=++tot,p[tot]=i;

	memset(f,-1,sizeof(f));int T=read();

	while(T--)

	{

		ll l=read(),r=read();

		cout<<Solve(r)-Solve(l-1)<<endl;

	}

	return 0;

}

巴特西

【CF55D】Beautiful numbers（动态规划）

【CF55D】Beautiful numbers（动态规划）

题面

题解

最新文章

热门文章