一、題目

點此看題

二、解法

首先一個數滿足被一堆數整除等價于這個數滿足被這一堆數的最小公倍數整除，$[1,9]$的最小公倍數是$2520$，且這個數有$48$個因數。

定義$dp[i][j][k][l]$，為$i$位，是否頂到上界，模$2520$的余數為$k$，現在的最小公倍數為$l$（映射之后存進去，最多$48$個），最后再判斷$k\%l=0$是否成立，成立就產生$1$的貢獻。

好像代碼我換了一個寫法，去掉了第二維，只記錄未頂到上界的$dp$值，頂到上界的$dp$值就自己去$dp$，不記錄。

#include <cstdio> #include <cstring> #define int long long const int M = 2525; const int jzm = 2520; int read() {int x=0,flag=1;char c;while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*flag; } int T,l,r,n,res,a[20],c[M],dp[20][M][50]; int gcd(int a,int b) {return !b?a:gcd(b,a%b); } int lcm(int a,int b) {if(!a || !b) return a|b;return a/gcd(a,b)*b; } int dfs(int x,int up,int y,int z) {if(x==0) return y%z==0;if(!up && dp[x][y][c[z]]!=-1) return dp[x][y][c[z]];int t=0;for(int p=0;p<=9;p++){if(up && p>a[x]) continue;t+=dfs(x-1,(up&&p==a[x]),(y*10+p)%jzm,lcm(z,p));}if(!up) dp[x][y][c[z]]=t;return t; } int cal(int x) {n=res=0;while(x) a[++n]=x%10,x/=10;return dfs(n,1,0,1); } signed main() {for(int i=1;i<=jzm;i++)if(jzm%i==0)c[i]=++n;T=read();memset(dp,-1,sizeof dp);while(T--){l=read();r=read();printf("%lld\n",cal(r)-cal(l-1));} }

總結

以上是生活随笔為你收集整理的CF55D Beautiful numbers的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。