BZOJ

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.