CF55D： Beautiful Number

传送门

一句话题意

求 l~r 之间有多少个数能整除自己各位上的数（排除 0 ）

分析

然后我们一看就知道数位 dp ，但是状态很难设计啊 QWQ

我们可以发现所有数位的 lcm 最大为 2520 （就是 1~ 9 的 lcm 嘛）

然后我们再看就能发现某个数模 2520 下如果能整除它所有数位的 lcm 那么它就是满足条件的数

也就是说一个数模其所有数位的 lcm 的结果和模 2520 后再去模这个 lcm 的结果是相同的

为什么？什么为什么，因为一个数所有数位的 lcm 必然是 2520 的因子啊

那么我们考虑令 f[i][j][k] 表示还剩 i 位没有处理，当前的数模 2520 为 j，当前所有数位的 lcm 为 k 的方案数，这样状态就设计出来了

然后就是代码了：（由于一开始不会抄的题解，所以写的是 dfs ，经过一个小时的奋斗终于写好了非 dfs 版的，就放上来了 QVQ ）

//by Judge

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define fp(i,a,b) for(int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(int i=(a),I=(b)-1;i>I;--i)

#define ll long long

using namespace std;

const int mod=2520;

#ifndef Judge

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

#endif

char buf[1<<21],*p1=buf,*p2=buf;

inline ll read(){ ll x=0,f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;

} char sr[1<<21],z[20];int C=-1,Z;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

inline void print(ll x,char chr='\n'){

    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]=chr;

} int tot,id[mod+50],val[50],d[21];

ll f[20][mod+3][50];

int GCD(int a,int b) { return b?GCD(b,a%b):a; }

int LCM(int a,int b) { return a/GCD(a,b)*b; }

void prep() {

	fp(i,1,mod) if(!(mod%i)) id[i]=++tot,val[tot]=i;

	fp(i,1,tot) fp(j,0,mod/val[i]) f[0][val[i]*j][i]=1;

	fp(i,1,19) fp(j,0,mod) fp(k,1,tot) fp(d,0,9)

		f[i][j][k]+=f[i-1][(j*10+d)%mod][id[d?LCM(val[k],d):val[k]]];

}

inline ll solv(ll x){

	int len=0; ll ans=0,Val=0,Lcm=1;

	for(;x;x/=10) d[++len]=x%10;

	fd(i,len,1){

		fp(j,0,d[i]-1) ans+=f[i-1][(Val*10+j)%mod][id[j?LCM(Lcm,j):Lcm]];

		Val=(Val*10+d[i])%mod,Lcm=d[i]?LCM(Lcm,d[i]):Lcm;

	} return ans+!(Val%Lcm);

}

int main(){ prep(); ll T=read(),l,r;

	fp(kkk,1,T) l=read(),r=read(),

		print(solv(r)-solv(l-1));

	return Ot(),0;

}

巴特西

CF55D： Beautiful Number

一句话题意

分析

最新文章

热门文章