1. CF1689D Lena and Matrix
题目描述
- ，先推一下式子。
- 原始： ∑ p ∈ p r i m e ∑ i = 1 n ∑ j = 1 n [ gcd ( i , j ) = = p ] \sum _{p∈prime}\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)==p] ∑p∈prime∑i=1n∑j=1n[gcd(i,j)==p]
- ①： ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ∑ j = 1 ⌊ n p ⌋ [ gcd ( i , j ) = = 1 ] \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)==1] ∑p∈prime∑i=1⌊pn⌋∑j=1⌊pn⌋[gcd(i,j)==1]
- ②： ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ( ( 2 ⋅ ∑ j = 1 i [ gcd ( i . j ) = = 1 ] ) − 1 ) \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot \sum_{j=1}^{i}[\gcd(i.j)==1])-1) ∑p∈prime∑i=1⌊pn⌋((2⋅∑j=1i[gcd(i.j)==1])−1)
- ③： ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ( ( 2 ⋅ φ ( i ) − 1 ) \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot\varphi(i) -1) ∑p∈prime∑i=1⌊pn⌋((2⋅φ(i)−1)
- ④： ∑ p ∈ p r i m e 2 ⋅ ( ∑ i = 1 ⌊ n p ⌋ φ ( i ) ) − 1 \sum _{p∈prime}2 \cdot(\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i))-1 ∑p∈prime2⋅(∑i=1⌊pn⌋φ(i))−1
所以可以使用线性筛预处理 φ \varphi φ 函数， 在预处理 φ \varphi φ 函数的前缀和.
O ( n ) O(n) O(n)时间复杂度求解.A C AC AC.