来自"NOCOW"

get(i)表示0到i的有几个满足要求的数

最后输出get(y)-get(x-1)

get(x)怎么算呢？

设pow[i]=B^i,

通过这一段代码

for i:=n downto 0 do 
    if l>=pow[i] then 
    begin 
      dec(l,pow[i]); 
      data[i]:=1; 
    end;

这是很像求二进制数啊，其实就是得出

x=data[n]*b^n+data[n-1]*b^(n-1)……data[0]*b^0; （*）

其中data[i]只能为0或1，我们用一点简单的组合公式就能算出比x小的，能表示成（*）式地，且data中1的个数不超过k个的

数有多少个。

program cao;
const
  maxn=50;
 
var
  pow,data,a:array[0..maxn] of qword;
  i,j,l,m,n,b,k,x,y,ans:longint;
 
function c(n,m:longint):qword;
var
  t:qword;
  i:longint;
begin
  if m>n then exit(0);
  if n<=0 then exit(0);
  if m<0 then exit(0);
  if n-m>m then m:=n-m;
  t:=1;
  for i:=m+1 to n do
    t:=t*i div (i-m);
  exit(t);
end;
 
function work(l:longint):qword;
var
  t:qword;
begin
  if l<=0 then exit(0);
  fillchar(data,sizeof(data),0);
  fillchar(a,sizeof(a),0);
  for i:=n downto 0 do
    if l>=pow[i] then
    begin
      dec(l,pow[i]);
      data[i]:=1;
    end;
  j:=0;
  for i:=n downto 0 do
    if data[i]=1 then
    begin
      inc(j);
      a[j]:=i;
    end;
  t:=0;
  for i:=1 to j do
    if k-i+1>0 then
    t:=t+c(a[i],k-i+1);
  if j>=k then inc(t);
  exit(t);
end;
 
begin
  read(x,y,k,b);
  pow[0]:=1;
  n:=0;
  while pow[n]<y do
  begin
    inc(n);
    pow[n]:=pow[n-1]*b;
  end;
  ans:=work(y)-work(x-1);
  if ans<0 then ans:=0;
  writeln(ans);
end.

{cloudygoose}
var
  i,j,k,l,m,n,b,x,y:longint;
  pow,a:array[0..50]of int64;
function cal(n,m:int64):int64;
var i:longint;
    ans:int64;
begin
  if m>n then exit(0);
  if m=0 then exit(1);
  ans:=1;
  for i:=1 to m do
    ans:=ans*(n-m+i) div i;
  cal:=ans;
end;
function work(l:int64):int64;
var
  i,num:longint;
  ans:int64;
begin
  fillchar(a,sizeof(a),0);
  num:=0;
  for i:=n downto 0 do
    if pow[i]<=l then
      begin
        l:=l-pow[i];
        inc(num);
        a[num]:=i;
      end;
  ans:=0;
  for i:=1 to num do
    if k-i+1>=0 then
      ans:=ans+cal(a[i],k-i+1);
{这句话表示先取a[1],a[2]...a[i-1]，然后在比a[i]小的次幂（注意有个0次方）中选剩下的几个}
 
  if num=k then inc(ans);
  work:=ans;
end;
begin
  assign(input,'1057.in');reset(input);
  read(x,y,k,b);
  pow[0]:=1; n:=0;
  while pow[n]<y do
    begin
      pow[n+1]:=pow[n]*b;
      inc(n);
    end;
  writeln(work(y)-work(x-1));
  close(input);
end.