这题，没想出来，根本没想到用最小公倍数来更新，一直想状态压缩，不过余数什么的根本存不下，看的von学长的，比着写了写，就是模版改改，不过状态转移构造不出，怎么着，都做不出来。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 #define LL __int64 6 #define MOD 2520 7 LL dp[31][2600][50]; 8 int index[3000]; 9 int num[31];10 LL gcd(LL a,LL b)11 {12     return b == 0?a:gcd(b,a%b);13 }14 LL lcm(LL a,LL b)15 {16     return a*b/gcd(a,b);17 }18 LL dfs(int pos,int pre,int mod,int bound)19 {20     int end,tpre,tmod,i;21     LL ans = 0;22     if(pos == -1)23     return pre%mod == 0;24     if(!bound&&dp[pos][pre][index[mod]] != -1)25     return dp[pos][pre][index[mod]];26     end = bound ? num[pos] : 9;27     for(i = 0;i <= end;i ++)28     {29         tpre = (pre*10 + i)%MOD;30         if(i)31         tmod = lcm(mod,i);32         else33         tmod = mod;34         ans += dfs(pos-1,tpre,tmod,bound&&i == end);35     }36     if(!bound)37     dp[pos][pre][index[mod]] = ans;38     return ans;39 }40 LL judge(LL x)41 {42     int pos = 0;43     while(x)44     {45         num[pos++] = x%10;46         x = x/10;47     }48     return dfs(pos-1,0,1,1);49 }50 int main()51 {52     int t,i,num = 0;53     LL x,y;54     memset(dp,-1,sizeof(dp));55     for(i = 1;i <= MOD;i ++)56     {57         if(MOD%i == 0)58         index[i] = num++;59     }60     cin>>t;61     while(t--)62     {63         cin>>x>>y;64         printf("%I64d\n",judge(y)-judge(x-1));65     }66     return 0;67 }