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
来源: http://www.bubuko.com/infodetail-2949097.html