两题是类似的，这里说一下bzoj1853
首先我们求出所有的幸运号码，注意如果存在x是y的倍数则x不算在内，避免之后重复计算
下面我们就要统计幸运号码的倍数了，这显然是要用到容斥原理的
但是幸运号码很多，如果直接暴力找几个幸运号码的公倍数做容斥原理弄会TLE的；
因此我们想到在搜索中剪枝，如果几个幸运号码的公倍数已经大于r，
那么我们一定不会再用这几个幸运号码和别的幸运号码求公倍数了
为了体现这个剪枝的威力，我们穷举幸运号码的时候应该从大往小搜索；
var b:array[..] of int64;
a:array[..] of longint;
m,t,k,i:longint;
s,x,l,r,ans:int64;
f:boolean; function gcd(a,b:int64):int64;
begin
if b= then exit(a)
else exit(gcd(b,a mod b));
end; procedure dfs(j,t:longint;x:int64);
var y:int64;
begin
if j= then
begin
if t mod = then ans:=ans+r div x-(l-) div x //容斥原理
else if t> then ans:=ans-r div x+(l-) div x
end
else begin
dfs(j-,t,x);
y:=x div gcd(b[j],x);
if double(b[j])*double(y)<=r then //double是防止爆int64
dfs(j-,t+,b[j]*y);
end;
end; begin
readln(l,r);
t:=;
x:=r;
while x<> do
begin
inc(t);
x:=x div ;
end;
fillchar(a,sizeof(a),);
m:=;
while a[]=- do
begin
s:=;
for i:= to t do
if a[i]= then s:=s*+
else if a[i]= then s:=s*+;
if s>r then break
else if s<> then
begin
f:=true;
for i:= to m do
if s mod b[i]= then
begin
f:=false;
break;
end;
if f then
begin
inc(m);
b[m]:=s;
end;
end;
k:=t;
while a[k]= do
begin
a[k]:=;
dec(k);
end;
inc(a[k]);
end;
dfs(m,,);
writeln(ans);
end.