cojR8

Source

好题:E

E

请先思考后再展开

几乎是抄了一遍题解系列……
$$
\begin{aligned}
ans&=\sum_{i=1}^n ( \prod p_t^{\lfloor k_t/2 \rfloor} )=\sum_{i=1}^n ( i/\prod p_t^{\lceil k_t/2 \rceil} ) \\
&=\sum_{i=1}^n \sum_{j=1}^i[i|j^2]=\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^{j^2} [ik=j^2] \\
&看到乘积为完全平方数,考虑最大公约数\\
&=\sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{k=1}^i [gcd(i,k)=1] [i,k为完全平方数] \\
&=\sum_{d=1}^n \sum_{i=1}^{\sqrt{n/d}} \sum_{k=1}^i [gcd(i^2,k^2)=1] \\
&=\sum_{d=1}^n \sum_{i=1}^{\sqrt{n/d}} \varphi(i^2)=\sum_{i=1}^n \varphi(i) \lfloor n/i^2 \rfloor
\end{aligned}
$$

F

请先思考后再展开

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b2c5.html
转载请注明出处,谢谢!