Codeforces 55D Beautiful numbers --- 数位DP - c++编程基础

一个数能被它的所有非零数位整除，则能被它们的最小公倍数整除，而1到9的最小公倍数为2520，其中可以是最小公倍数的其实只有48个，先存下来，不然超内存。

dfs中的 n 表示之前那些位的最小公倍数

mod记录对2520取模的值，要直接拿一个很大的数对所有位的最小公倍数取模不现实，这里又用到了上次说的一个数论知识：如果两个数同余，那么对这两个数作任何相同运算，结果还是同余。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #define inf 0x3f3f3f3f #define ll __int64 using namespace std; ll dp[20][50][2521]; int num[20],cnt,t[200]; int gcd(int a,int b) { while(a%b) { int tmp=b; b=a%b; a=tmp; } return b; } int lcm(int a,int b) { if(b==0) return a; return a/gcd(a,b)*b; } int sear(int x) { int mid,bot=0,top=cnt; while(bot+1!=top) { mid=bot+top>>1; if(t[mid]>x) top=mid; else bot=mid; } return bot; } ll dfs(int n,int pos,int mod,int flag) { if(pos==-1) return (mod%t[n]) 0:1;//--- if(!flag&&dp[pos][n][mod]!=-1) return dp[pos][n][mod]; ll ans=0;int p,i; if(flag) p=num[pos]; else p=9; for(i=0;i<=p;i++) ans+=dfs(sear(lcm(t[n],i)),pos-1,(mod*10+i)%2520,flag&&i==p); if(!flag) dp[pos][n][mod]=ans; return ans; } ll cal(ll x) { int l=0; while(x) { num[l++]=x%10; x/=10; } return dfs(0,l-1,0,1); } void init() { cnt=0; for(int i=1;i<=2520;i++) if(2520%i==0) t[cnt++]=i; } int main() { int t; ll a,b; init(); memset(dp,-1,sizeof dp); scanf("%d",&t); while(t--) { scanf("%I64d%I64d",&a,&b); printf("%I64d\n",cal(b)-cal(a-1)); } return 0; }