如有乱码，请。

 

题目描述

给出两个数a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

输入格式

一行，两个整数a和b

输出格式

一个整数，表示答案

输入输出样例

输入 #1复制

10 19

输出 #1复制

3

说明/提示

对于所有的数据，1 ≤ a ≤ b ≤ 10^{18}1≤a≤b≤1018

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;long long dp[20][201][201],bit[21],a,b,MOD;long long dfs(int p,int sum,int mod,int limt){//数位dp模板，被我改了点小地方 if(p==0){ if(mod==0&&sum==MOD) return 1; else return 0;} int up=limt?bit[p]:9; if(!limt&&dp[p][sum][mod]!=-1)return dp[p][sum][mod]; long long ret=0; for(int i=0;i<=up;++i) ret+=dfs(p-1,sum+i,(mod*10+i)%MOD,limt&&up==i); if(!limt) dp[p][sum][mod]=ret;return ret;}long long solve(long long n){ int len=0,mod=0; while(n){mod+=n%10; bit[++len]=n%10;n/=10;} long long ret=0; for(MOD=1;MOD<=len*9;MOD++){//枚举 memset(dp,-1,sizeof(dp)); //这里必须清，当然，清成什么取决于你 ret+=dfs(len,0,0,1); } return ret;}int main(){ scanf("%lld%lld",&a,&b); printf("%lld",solve(b)-solve(a-1)); return 0;}