16.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——幾種選法一條除法直接得出(16.2 的數學性質又立功),第三層迴圈整層消失: