传送门
被几个数整除, 等价于被他们的 lcm 整除.
于是想到设 dp[i][j][k] 表示到第 i 位, 当前的数为 j,lcm 为 k 的数的个数.
这样空间肯定无法接受. 考虑优化.
我们发现 1,2,3,4,5,6,7,8,9 的 lcm 不过是 2520, 我们每次把 j% 一下 2520 不会影响答案.
然后对于 k 这一维, 直接存下当前的 lcm 也是不行的.
我们发现在真正由 1,2,3,4,5,6,7,8,9 构成的 lcm(也就是 2520 的约数) 其实很少, 只有 48 个.
于是我们开个数组映射一下即可.
然后小心爆 int.
- #include<bits/stdc++.h>
- #define LL long long
- #define INF 2100000000
- #define mod 2520
- using namespace std;
- LL read()
- {
- LL x=0,f=1;char s=getchar();
- while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
- while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
- return x*f;
- }
- void print(LL x)
- {
- if(x<0)x=-x,putchar('-');
- if(x>9)print(x/10);
- putchar(x%10+'0');
- }
- LL T;
- LL cnt=0,tot=0;
- LL dp[20][mod+2][50];
- LL num[20];
- LL a[mod+1];
- LL gcd(LL a,LL b)
- {
- if(b==0)return a;
- return gcd(b,a%b);
- }
- LL LCM(LL x,LL y)
- {
- if(!y)return x;
- return x/gcd(x,y)*y;
- }
- LL dfs(LL x,LL shu,LL lcm,LL lim)
- {
- if(!x)return (shu%lcm==0)?1:0;
- if(dp[x][shu][a[lcm]]!=-1&&!lim)return dp[x][shu][a[lcm]];
- LL maxx=lim?num[x]:9;
- LL res=0;
- for(LL i=0;i<=maxx;++i)
- res+=dfs(x-1,(shu*10+i)%mod,LCM(lcm,i),(i==maxx)&&lim);
- if(!lim)dp[x][shu][a[lcm]]=res;
- return res;
- }
- LL solve(LL x)
- {
- tot=0;
- memset(num,0,sizeof(num));
- while(x)
- {
- num[++tot]=x%10;
- x/=10;
- }
- return dfs(tot,0,1,1);
- }
- int main()
- {
- T=read();
- for(LL i=1;i<=mod;++i)
- if(mod%i==0)a[i]=++cnt;
- memset(dp,-1,sizeof(dp));
- while(T--)
- {
- LL l=read(),r=read();
- printf("%lld\n",solve(r)-solve(l-1));
- }
- }
- /*
- 5
- 4 8
- 12 34
- 56784 1356234
- 122 556
- 23 24
- */
- View Code
来源: http://www.bubuko.com/infodetail-3285188.html