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