BZOJ 3560

传送门

Orz PoPoQQQ 里面似乎有些错误的说

首先把每个$a_i$分解质因数,分解成各个质因子的次幂相乘

假设分解后某个质数$p$在每个$a_i$中的次数分别是$b_i$,那么$p$对答案的贡献就是 (注意:这个式子及以下的式子仅对于一个质数$p$而言)

$$\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\cdots \sum_{i_n=0}^{b_n}\varphi(p^{\sum_{j=1}^n i_j})$$

例如对于样例数据$6,10,15$,将三个数中的质因数$2,3,5$分开以后所有情况如下表所示

2 3 5
$2^0 2^0 2^0$ $3^0 3^0 3^0$ $5^0 5^0 5^0$
$2^0 2^0 2^1$ $3^0 3^0 3^1$ $5^0 5^0 5^1$
$2^0 2^1 2^0$ $3^1 3^0 3^0$ $5^0 5^1 5^0$
$2^0 2^1 2^1$ $3^1 3^0 3^1$ $5^0 5^1 5^1$

三列中每列挑一个三元组组合起来就是一组合法解 例如第一列第三行 第二列第一行 第三列第四行组合起来就是$(1,10,5)$

上表对应的$\varphi$为

2 3 5
$\varphi(1)=1$ $\varphi(1)=1$ $\varphi(1)=1$
$\varphi(2)=1$ $\varphi(3)=2$ $\varphi(5)=4$
$\varphi(2)=1$ $\varphi(3)=2$ $\varphi(5)=4$
$\varphi(4)=2$ $\varphi(9)=6$ $\varphi(25)=20$

因为$\varphi$是积性函数且质因数肯定两两互质,所以这些$\varphi$是可以直接相乘的,对于$(1,10,5)$的答案就是$1*1*20=20$

所以就得到了上面那个式子

根据$\varphi(x^k)=\varphi(x)*x^{k-1}=(x-1)*x^{k-1}$($x$为质数且$k\geq 1$)变形一下,原式搞成

$$((\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\cdots \sum_{i_n=0}^{b_n}p^{\sum_{j=1}^n i_j})-1)\times \frac{p-1}{p}+1$$

其中$-1$再$+1$是为了特判$p$的指数为$0$的情况

然后继续搞一搞,搞成

$$((\prod_{i=1}^n \sum_{j=0}^{b_i} p^j)-1)\times \frac{p-1}{p}+1$$

咦,只跟当前的$p$有关耶,而且$p^j$似乎可以预处理吧…

那么问题就解决了

将$a_i(i\in [1,n])$每个都分解质因数,把质因数和它的指数存起来,然后放在一起排个序

每次处理一个质因子$p$(因为排过序了所以在数组里是连续的一段),然后根据上面的式子搞一搞就出来了~


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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
program bzoj_3560;
const mo=1000000007;
type rec=record a,p:longint; end;
var s:array[1..2500000]of rec;
n,a,i,j,tot:longint;
ans:int64;
pre:array[0..100]of int64;
procedure count(x:longint);
var i:longint;
begin
for i:=2 to trunc(sqrt(x)) do if x mod i=0 then
begin
inc(tot);
s[tot].a:=i;
while x mod i=0 do
begin
inc(s[tot].p);
x:=x div i;
end;
end;
if x<>1 then
begin
inc(tot);
s[tot].a:=x;
s[tot].p:=1;
end;
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,p:rec;
begin
i:=l;
j:=r;
mid:=s[(l+r)>>1];
repeat
while (s[i].a<mid.a)or((s[i].a=mid.a)and(s[i].p<mid.p)) do inc(i);
while (s[j].a>mid.a)or((s[j].a=mid.a)and(s[j].p>mid.p)) do dec(j);
if i<=j then
begin
p:=s[i];
s[i]:=s[j];
s[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function qp(x,p:longint):int64;
var pre:int64;
begin
qp:=1;
pre:=x;
while p<>0 do
begin
if p and 1=1 then qp:=(qp*pre)mod mo;
pre:=(pre*pre)mod mo;
p:=p>>1;
end;
end;
procedure calc(l,r:longint);
var i:longint;
p:int64;
begin
pre[0]:=1;
for i:=1 to s[r].p do pre[i]:=(pre[i-1]*s[l].a)mod mo;
for i:=1 to s[r].p do pre[i]:=(pre[i]+pre[i-1])mod mo;
p:=1;
for i:=l to r do p:=(p*pre[s[i].p])mod mo;
if p=1 then p:=mo else dec(p);
p:=(((p*qp(s[l].a,mo-2))mod mo)*(s[l].a-1)+1)mod mo;
ans:=(ans*p)mod mo;
end;
begin
readln(n);
tot:=0;
for i:=1 to n do
begin
readln(a);
count(a);
end;
qsort(1,tot);
i:=1;
ans:=1;
while i<=tot do
begin
j:=i;
while (j<tot)and(s[j+1].a=s[i].a) do inc(j);
calc(i,j);
i:=j+1;
end;
writeln(ans);
end.