HDU 3208 Integer's Power

在 HDU OJ 看 problem title 隨便挑的一題...
據 AC rate 判定這題值得一做

---

題意：

對於正整數 x = b^e，其中 b、e 為正整數
定義 x (≥ 2) 的 integer power 為 e 的最大可能值
（81 的 integer power 是 4，不是 2）

給定正整數 2 ≤ A ≤ B ≤ 10¹⁸
求 [A, B] 區間內所有正整數的 integer power 的總和

---

分析：

稍為簡化問題：
令 f(Y) := [1, Y] 區間所有正整數的 integer power 總和
則答案 = f(B) - f(A - 1)

留意到 integer power 的最大可能值為 59
我們可以枚舉 e := 1 至 59

令 cnt[e] := 在 [1, Y] 區間之中 integer power 是 e 的整正數的個數
gagCnt[e] := 在 [1, Y] 中可以表示成 b^e 的整正數的個數

易知

gagCnt[e] = floor(Y^1/e)

── 把 1 納入考慮範圍沒所謂... 因為 1 會被 f(B) 及 f(A-1) 互相抵消

若我們能修正 gagCnt[e] 的數值去得出 cnt[e]
（例如，要在 cnt[2] 中要排除對 81 的考慮）
那就得到答案了：

f(Y) = ∑_e∈[1,59] cnt[e] × e

所以... 接下來要解決：

1. 處理重計（從 gagCnt[] 得到 cnt[]）
   
2. 小心 overflow（哪個時候多了這項？）

---

算法：

對於 1.
相信很多人會很快想起 容斥原理 (Inclusion-exclusion principle)

若直接應用... 2⁶⁰ 似乎太大
而... 因數的交集又似乎沒那麼大... 容斥不是完全沒可能
不過算吧，反正我沒有仔細地想一去...
不過總之，我最後導出以下的算法：

On input Y /* function f(Y) */
For i := 1 to 59
cnt[i] ← floor(Y^1/e) /* 這一步小心implement... 處理 overflow */
EndFor
For i := 59 to 2
For j := 1 to i
cnt[j / i] ← cnt[j / i] - cnt[i]
EndFor
EndFor
Return ∑_e∈[1,59] cnt[e] × e

以上 pseudo-code 亦是程式核心
為甚麼這樣計？這個有點難用文字表述...

──嘛... 其實背後精神和 容斥 大概沒有兩樣

只是對於 整除(divides) 這關係，[1, 59] 形成了一個 DAG...

---

對於 2.
我一開始我少瞧了它...

先用 pow(double, double) 給 cnt[e] 作一個粗略評估
然後再上下調整數值這方向準沒錯

只是... 我栽在 overflow 的偵測...

第一段 AC 的 code
用兩個 long long int 模擬 big integer
外加了一些嘔心的 if-then-else...

第二段 AC 的 code 比較聰明了
對於 b^e 的計算，沒有使用 repeated squaring
改為 e 次乘法，當發現 ≤ 0 ⇒ overflow（return 無限大）

不過... 這是否足夠？所有 overflow 都會被偵測出來嗎？
明天要再跟 Chin 多討論討論

---

測試數據：

具體數值請自己用電腦或紙筆計算

942293338086516350
cnt[28] 是 4
小心別算出 - 5^28 ( > 10¹⁸)
應該是 4^28