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…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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.