这是一道比较难的数位dp
因为逐位统计好像无法处理数位和整除原数的
但是有了刚才的bzoj1072的经验，我们能做的是逐位处理被一个数d整除的方案
不难想到先穷举数位和now，now最大也就162，可以承受
然后在统计数位和为now且能整除原数的方案
我们用f[less,i,j,k]表示第i位是否必须小于n的第i位，还有i位没处理，当前数位和为j，处理过的数位mod now余数为k的方案
然后记忆化搜索就可以了（转移见程序）
var f:array[..,..,..,..] of int64;
a:array[..] of longint;
len,t,now,i:longint;
l,r,ans:int64; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function calc(p,i,j,k:longint):int64;
var w,ch,s,t:longint;
sum:int64;
begin
sum:=;
if i= then
if (j=) and (k=) then exit()
else exit();
if f[p,i,j,k]<>- then exit(f[p,i,j,k]); //记忆化
s:=max(,j-*(i-));
if p= then t:=a[i] else t:=;
for w:=s to t do //穷举这位的数
begin
if (p=) and (w=a[i]) then ch:=
else ch:=;
sum:=sum+calc(ch,i-,j-w,((k* mod now)+w) mod now); 转移
end;
f[p,i,j,k]:=sum;
exit(sum);
end; procedure work(x:int64);
begin
t:=;
while x<> do
begin
inc(t);
a[t]:=x mod ;
x:=x div ;
end;
end; function count(p:int64):int64;
begin
work(p);
fillchar(f,sizeof(f),);
exit(calc(,t,now,));
end; begin
readln(l,r);
len:=trunc(ln(r)/ln())+;
for now:= to do
begin
if now>len* then break; //小优化
ans:=ans+count(r)-count(l-);
end;
writeln(ans);
end.