\(S\) の長さを \(k\) とします。\(k=1\) のとき \(X \ge 1\) より条件を満たすことはありません。

\(k=2\) の場合

・\(S_1\) を固定します。すると、\(a - b = \frac{X}{S_1}\) である必要があります。よって、\(S_1\) は \(X\) の約数である必要があります。このとき、\((a,b,S_2)\) の条件は以下の通りです。

• $a - b = \frac{X}{S_1}$
• $S_1 < b$
• $a \le N$
• $S_2 \le \min(9,a,b)$

\(b\) を固定すれば \(a\) は定まるため、\(S_1 < b \le N - \frac{X}{S_1}\) を満たす \(b\) に対して \(\min(10,b)\) の総和を取ればよいです。これは \(\mathrm{O}(1)\) で出来ます。

\(k \ge 3\) の場合

\(a^k - b^k \equiv 0 \bmod (a - b)\) が成り立つため \(a-b\) は \(X\) の約数である必要があります。ここで、\(s = a - b\) とします。すると、\(a^2 - b^2 \le X\) である必要があるため、\(2sb + s^2 \le X\) を満たす必要があります。よって、\((a,b)\) の組としてあり得るものは \(\mathrm{O}(X\log X)\) 個です。

さて、\((a,b)\) の組を \(1\) 個固定した場合条件を満たす \(S\) の個数を動的計画法で求めても \(a^k - b^k \le X\) を満たす \(k\) はかなり小さいため間に合いますが、実は条件を満たす \(S\) は高々 \(1\) 個であることが証明できます。

証明：任意の \(k(\ge 1)\) に対して \(a^k - b^k > (b-1)(\sum_{i=0}^{k-1} a^i - b^i)\) を示せれば \(S\) から貪欲に \(a^k - b^k\) を引くしかないため条件を満たす \(S\) が高々 \(1\) 個かつ 判定を \(\mathrm{O}(\log X)\) で行うことが出来る。また、実際この式は式変形により成り立つことが証明出来る。

よって、\(k \ge 3\) の場合を \(\mathrm{O}(X\log^2 X)\) で解くことが出来ます。実際は \((a,b)\) の組の候補がより少ないことや、\(a^k - b^k \le X\) を満たす \(k\) が小さいことなどからより高速に動作します。

よって、全体でこの問題を \(\mathrm{O}(X\log^2 X)\) で解くことが出来ます。