题解 P6825 【「EZEC-4」求和】

是一道锻炼卡常水平的好题！ 先推柿子 $$ \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nd^{i+j}[gcd(i,j)=d] $$ $$ \sum_{d=1}^n\sum_{i=1}^{\lfloor{n/d\rfloor}}\sum_{j=1}^{\lfloor{n/d\rfloor}}d^{di+dj}[gcd(i,j)=1] $$ $$ \sum_{d=1}\sum_{k=1}\mu(k)\sum_{i=1}^{\lfloor{n/dk\rfloor}}d^{idk}\sum_{j=1}^{\lfloor{n/dk\rfloor}}d^{jdk} $$ 考虑加上$dk\le n$的条件，答案不变 $$ \sum_{d=1}\sum_{k=1}^{\lfloor n/d\rfloor}\mu(k)\sum_{i=1}^{\lfloor{n/dk\rfloor}}d^{idk}\sum_{j=1}^{\lfloor{n/dk\rfloor}}d^{jdk} $$ 前面两个合起来是调和级数，后面就等比数列求和爆算，复杂度$\mathcal O(n\log n\log p)$ 可得50分。 发现等比数列求和那里$\mathcal O(\log p)$是因为求逆元。那么不妨**离线求逆元**，那就只有一个快速幂的复杂度了，总共就是$\mathcal O(n\log^2 n)$. 另外，直接离线求逆元空间不够，分成若干段，每段长度$10^6$去算就好。 努力卡常即可AC。[code](https://pasteme.cn/51851) PS:后来有人一通积分证出来是$\mathcal O(n\log n)$的。 ~~PPS:加了一堆快速取模等优化，我卡进了最优解第一页，一起来卡常啊~~