Gym 101981J – Prime Game

题目链接:Gym – 101981J,ICPC 2018 南京赛区现场赛J题

[2019年6月16日更新] 计蒜客上过了,更新优化后的代码。

题目要求计算

$$\sum_{i = 1}^{n} \sum_{j = i}^{n} f(i,j)$$

其中$f(i,j)$表示$\prod_{k = i}^{j} a_k$中质因子的个数($n, a_i \leq 10^6$)。

考虑样例给的10个数的情况,实质是对表里的所有$f(x,y)$求和

我们可以反向考虑,考虑每个质因子对表里的$f(x,y)$的贡献。首先我们可以对每一个$a_i$做质因数分解,用一个类似于邻接表的结构记录每个质因子出现在第几个数的位置,例如$a_2 = 62$,质因子有$\{2,31\}$,$a_3 = 10$,质因子有$\{2,5\}$,$a_{10} = 24$,质因子为$\{2,3\}$(样例一中只有这三个数字有质因子$2$),那么我们可以记录下${\rm pos} (2) = \{ 2,3,10 \}$。本着不重复计算的原则,实际上$2$的贡献就是涂色部分全部$+1$:

最终我们归纳到,对于每个质因子$p$,对答案的贡献为

$$\sum_{i = 1}^{{\rm size\, of\, pos}(p)} [{\rm pos}(p, i) – {\rm pos} (p, i – 1)] \times [n – {\rm pos}(p, i) + 1]$$

Codeforces上670ms/2000ms通过,计蒜客 TLE/1000ms。

考虑这样优化:其实对于${\rm pos}(i)$里的每个元素,我们只关心它的前一个元素是什么,实际上我们只要动态维护每个$i$的最后一个元素,然后每次push_back的时候直接先算贡献,算完覆盖掉即可。这里质因数分解也不需要预处理,直接分解即可(复杂度成迷==?)。

最终Codeforces 343ms/2000ms,计蒜客 401ms/1000ms。

说点什么

avatar
50
  Subscribe  
提醒