BZOJ 3930

传送门

Orz伟大领袖lzy

从$[L,H]$中取$n$个数，设这$n$个数为$a_1,a_2,\cdots,a_n$,设

$$F(k)=\sum_{a_1=L}^H \sum_{a_2=L}^H \cdots \sum_{a_n=L}^H=[k \mid gcd(a_1,a_2,\cdots,a_n)]$$

$$f(k)=\sum_{a_1=L}^H \sum_{a_2=L}^H \cdots \sum_{a_n=L}^H=[k=gcd(a_1,a_2,\cdots,a_n)]$$

那么

$$F(k)=\sum_{d \mid k}f(d)$$

$$f(k)=\sum_{k \mid d}\mu(\frac{d}{k})F(d)$$

然后搞一搞$F(k)$

$$F(k)=\sum_{a_1=\lfloor\frac{L-1}{k}\rfloor}^{\lfloor\frac{H}{k}\rfloor} \sum_{a_2=\lfloor\frac{L-1}{k}\rfloor}^{\lfloor\frac{H}{k}\rfloor} \cdots \sum_{a_n=\lfloor\frac{L-1}{k}\rfloor}^{\lfloor\frac{H}{k}\rfloor}[1 \mid gcd(a_1,a_2,\cdots,a_n)]$$

$$F(k)=(\lfloor\frac{H}{k}\rfloor-\lfloor\frac{L-1}{k}\rfloor)^n$$

然后

$$f(k)=\sum_{d’=1}^{\lfloor\frac{H}{k}\rfloor}\mu(d’)(\lfloor\frac{H}{d’\cdot k}\rfloor-\lfloor\frac{L-1}{d’\cdot k}\rfloor)^n$$

直接求当然会挂的很惨…

对此，PoPoQQQ的解法是搞$\mu$的前缀和然后搞个阈值然后blabla…

后面那一坨是会出现很多$0$的，所以我们把$=0$的部分跳过去，光计算不等于$0$的时候的$\mu$值，直接用$\mu$的定义来算，而在极限数据中不等于$0$的最多就有$5w$个，所以这样的效率是$O(n^{1/2}+(5w)^{3/2})$效率是$0.2s$左右。 ——lzy

跪烂了Orz…

program bzoj_3930;
const mo=1000000007;
var n,k,l,h:int64;
 
function min(a,b:int64):int64;
begin
  if a<b then exit(a) else exit(b);
end;
 
function qp(x,k:int64):int64;
var p:int64;
begin
  p:=x;
  qp:=1;
  while k<>0 do
  begin
    if k and 1=1 then qp:=(qp*p)mod mo;
    p:=(p*p)mod mo;
    k:=k>>1;
  end;
end;
 
function mu(x:longint):longint;
var i:longint;
begin
  mu:=1;
  for i:=2 to trunc(sqrt(x)) do while x mod i=0 do
  begin
    x:=x div i;
    mu:=-mu;
    if x mod i=0 then exit(0);
  end;
  if x<>1 then mu:=-mu;
end;
 
procedure calc;
var i:longint;
    ans,q:int64;
begin
  ans:=0;
  i:=1;
  while i<=h do
  begin
    q:=qp(h div(i*k)-(l-1)div(i*k),n);
    if q<>0 then ans:=(ans+mu(i)*q+mo)mod mo else
    if (l-1)div i<>0 then i:=min(h div(h div i),(l-1)div((l-1)div i)) else i:=h div(h div i);
    inc(i);
  end;
  writeln(ans);
end;
 
begin
  readln(n,k,l,h);
  calc;
end.