文件详细信息

下载本文件

本文件的大小为 886 字节。

#include<cstdio>
#include<cstring>
typedef long long ll;
int min(int a,int b){
	return a<b?a:b;
}
ll a,b;
int digits[22],cnt;
ll f[19][162][163];
ll dfs(int digit,int sum,int remainder,int now,int flag){
	if(digit==-1)return sum==now&&!remainder;
	if(sum+(digit+1)*9<sum)return 0;
	if(!flag&&digit<19&&f[digit][remainder][now]!=-1)return f[digit][remainder][now];
	ll ans=0;
	int d=flag?digits[digit]:9;
	for(int i=0;i<=d&&now+i<=sum;i++)ans+=dfs(digit-1,sum,(remainder*10+i)%sum,now+i,flag&&i==d);
	if(!flag&&digit<19)f[digit][remainder][now]=ans;
	return ans;
}
ll solve(ll n){
	cnt=0;
	for(int i=0;i<22;i++)digits[i]=0;
	while(n){
		digits[cnt++]=n%10;
		n/=10;
	}
	ll ans=0;
	for(int i=1;i<=cnt*9;i++){
		memset(f,-1,sizeof(f[0])*min(cnt+1,19));
		ans+=dfs(cnt,i,0,0,1);
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&a,&b);
	a--;
	printf("%lld\n",solve(b)-solve(a));
	return 0;
}