PE 501

白送两个成就啊!

一看到题,感觉只能用暴力筛法了。。。

然后搜了paper。。?

发现素数函数竟然可以\(O(n^{\frac 12 + \varepsilon})\)求!

然后又发现github上的一个库,实现了一个\(O(n^{\frac23})\)的算法

用了一下,30s出解了

然后发现那个解决最新题的成就竟然是永久的!

W{IZ20GU9H[~3CLE5(7@`{D

A Proof of Menon’s Identity Using Burnside’s Lemma

$$\sum_{i=1}^n [\gcd(i,n)=1] \gcd(i-1,n) = \varphi(n) d(n)$$

第一次看到这个式子的时候,我就觉得非常神奇。\(i\)与\(n\)的互素关系竟然和\(i-1\)与\(n\)的最大公约数如此优美的联系!

然而,我看到这个等式的证明以后,更加地被震撼了!

Continue reading A Proof of Menon’s Identity Using Burnside’s Lemma