[ABC322G] Two Kinds of Base

感觉很难入手的样子。凭借感觉认为合法的 \((a, b)\) 很少，先把 \(k = 2\) 另外算，然后注意到 \(S_1 > 0\)，则 \(f(S, a) - f(S, b) \ge a^2 - b^2 = 2(a-b)b + (a-b)^2\)。又注意到 \(a-b\) 必是 \(X\) 的约数，由此 \(a-b \le X\)。那么根据经典的调和级数合法的 \((a,b)\) 只有 \(O(X \log X)\) 对，可以直接枚举。

注意到题目其实是两个不同进制数相减的问题，我们看作对应位权相减，第 \(i\) 位位权最终位 \(a^i - b^i\)。考虑这东西的性质，发现有 \(a^n - b^n \ge a^{n-1}b - b^n = b(a^{n-1} - b^{n-1})\)，于是不同位间没有进位这一说。故对于一组 \((a,b)\)，合法的 \(S\) 至多只有一组，且可以直接通过贪心得到。这样直接枚举 \((a,b)\) 贪心判断是否存在贡献即可做到 \(O(X \log ^2 X)\)。