题解：P17238 『STA - R10』Petal Dance
喵仔牛奶
·
·
题解
做法来自 GPT 5.6 Sol。
简单推一下式子发现问题可以变为对每个 k\in[1,n] 求 \sum_{i=1}^n\sum_{j=1}^n[k\mid ij]，推一下式子：
\begin{aligned}
& \sum_{i=1}^n\sum_{j=1}^n[k\mid ij] \\
=& \sum_{i=1}^n\left\lfloor\frac{n}{k/\gcd(i,k)}\right\rfloor \\
=& \sum_{pq=k}\lfloor\frac{n}{q}\rfloor\sum_{i=1}^{\lfloor n/p\rfloor}[\gcd(i,q)=1] \\
\end{aligned}
考虑对所有满足 pq\le n 的 p,q 求出 f(p,q)=\sum_{i=1}^{\lfloor n/p\rfloor}[\gcd(i,q)=1]。q=1 的情况平凡。令 x 为 q 的最小质因子，若 x\mid(q/x) 则 f(p,q)=f(p,q/x)，否则 f(p,q)=f(p,q/x)-f(px,q/x)。
用一些方法存下来递推即可，复杂度 \mathcal O(n\log n)。卡常后可以通过。