digitdp3.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int dp[20][2][200][20];

int findDigitsDividedBy(string &s,int curr, int flg,int digitSum,int digit){
	if(curr==s.length()){
		if(digit==0){
			return 0;
		}
		if(digitSum%digit ==0){
			return 1;
		}
		return 0;
	}

	if(dp[curr][flg][digitSum][digit]!=-1){
		return dp[curr][flg][digitSum][digit];
	}

	int limit = flg==1? s[curr]-'0' : 9;
	int ans =0;
	for(int i=0;i<=limit;i++){
		if(digit==0 && i==0){
			ans=ans+findDigitsDividedBy(s,curr+1,0,digitSum+i,digit);
		}
		else{
			int updatedFlg= (i==limit ? flg : 0);
			ans=ans+findDigitsDividedBy(s,curr+1,updatedFlg,digitSum+i,digit+1);
		}
	}
	return dp[curr][flg][digitSum][digit] = ans;
}


int main(){
	long long int l,r;
	cin>>l>>r;
	memset(dp, -1, sizeof(dp));
	string right= to_string(r);
	int rightans = findDigitsDividedBy(right,0,1,0,0);
	memset(dp, -1, sizeof(dp));
	string left= to_string(l-1);
	int leftans = findDigitsDividedBy(left,0,1,0,0);
	cout<<rightans-leftans<<endl;
	return 0;
}