極私的極彩色アンサー - TOGENASHI TOGEARI ——from K*(K8)

我怎么每天早上補昨天沒寫完的鮮花。

算了，放到今天吧。

書接上回

8. 發現 2 開了，和冪次沒關系了。

   發現有 \(b-a+1\) 個數，猜到是區間。

   考慮 \(p\) 和分布位置，可知是質數。

   線性篩即可。

9 10. 值域偏大，可以用 Miller_Rabin

11. 也是 \(2\) 開，結合 \(+-0\) 和長得像 \(\mu\) 的 \(u\) 是可以猜出是 \(\mu\) 的

    線性篩即可。

12 13.

發現值域達到 \(10^{18}\)，考慮快速判 \(\mu\)

\(l\) 指區間長度

首先先篩出 \(10^6\) 以內所有質數，在將區間的數中可以整除的除去，同時記錄因數個數 \(O(10^6\log l)\)

考慮 \(10^{18}\) 以內的數最多有 \(2\) 個因數大于 \(10^6\) 次冪，所以剩下的數只可能是：一個質數，一個平方數，一個有兩個質因子的數，\(1\)。

我們只需要知道質因子個數，所以可以將其 \(O(1)\) 分類，總復雜度 \(O(l)\)

有點卡常

（因為不會編排數字，干脆擺爛）