17.7 改變枚舉順序：A×B×C

壓軸是 AtCoder ARC113 A - A*B*C：給 K \le 2 \times 10^5，數出有幾組正整數三元組 (A, B, C) 滿足 A \times B \times C \le K（順序不同算不同組）。例如 K = 2 的答案是 4：(1,1,1)、(1,1,2)、(1,2,1)、(2,1,1)。

直覺做法：三重迴圈枚舉 (A, B, C) 逐組檢查——K^3 = 8 \times 10^{15} 次，10.1 三步驟一估就知道連想都不用想。

換個枚舉順序：只枚舉 A 和 B，C 用算的。固定 A、B（A \times B \le K）之後，C 能選 1, 2, \ldots, \left\lfloor \dfrac{K}{A \times B} \right\rfloor——幾種選法一條除法直接得出（17.2 的數學性質又立功），第三層迴圈整層消失：

¶完整程式碼

#include <iostream>
using namespace std;

int main() {
    int k;
    cin >> k;
    long long ans = 0;
    for (long long a = 1; a <= k; a++) {
        for (long long b = 1; a * b <= k; b++) {
            ans += k / (a * b);            // C 有 floor(K / (A*B)) 種選法
        }
    }
    cout << ans << '\n';
    return 0;
}

執行結果（輸入 2）：

4

這樣要跑幾圈？內層對每個 A 最多跑 \dfrac{K}{A} 圈，總圈數是

這串和大約是 K \times \log K 等級——又是 \log！（它就是喜歡在「除法、砍半、切塊」的場景冒出來。）本站實測 K = 2 \times 10^5 總共約 2.4 \times 10^6 圈、0.01 秒內跑完。從 8 \times 10^{15} 到 2.4 \times 10^6——改變枚舉順序＋一條除法，十億倍的差距。

為什麼那串和恰好是 K \log K 等級？完整的推導在 AA 競程的公開影片 Level 1 試聽課 03：以 ARC113 A 作為用數學方法計算時間複雜度的範例——這題正是 Level 1 開場的招牌例題，先解掉再看影片，收穫最大。