LOJ6241 性能优化

题意

求 $$T = \sum_{1\le i\le n}\sum_{1\le j\le\lfloor \frac{n}{i} \rfloor}\sum_{1\le k\le j}[\gcd(j,k)=1]$$ 多组数据 $n\le 10^{10^6}$

题解

$$T = \sum_{1\le i\le n}\sum_{1\le j\le\lfloor \frac{n}{i} \rfloor}\varphi(j)$$ 令 $$\text{S}(n) = \sum_{1\le i\le n}\varphi(i)$$ 则有 $$\begin{aligned} T &= \sum_{1\le i\le n}\text{S}(\lfloor \frac{n}{i} \rfloor) \\ &= \text{S}(n) + \sum_{2\le i\le n}\text{S}(\lfloor \frac{n}{i} \rfloor) \\ \end{aligned}$$ 根据杜教筛，由 $\varphi*\text{I}=\text{Id}$，有 $$\text{I}(1)\times \text{S}(n)=\sum_{1\le i\le n}\text{Id}(i)-\sum_{2\le i\le n}\text{S}(\lfloor\frac{n}{i}\rfloor)\times \text{I}(i)$$ 即 $$\text{S}(n)=\frac{n(n+1)}{2}-\sum_{2\le i\le n}\text{S}(\lfloor\frac{n}{i}\rfloor)$$ 带回原式得 $$\begin{aligned} T=&\frac{n(n+1)}{2}-\sum_{2\le i\le n}\text{S}(\lfloor\frac{n}{i}\rfloor) + \sum_{2\le i\le n}\text{S}(\lfloor \frac{n}{i} \rfloor)\\ =&\frac{n(n+1)}{2} \end{aligned}$$