Let \(k\) be the length of \(S\). If \(k-1\), then \(X \ge 1\), so the conditions are never satisfied.

If \(k=2\)

・Fix \(S_1\). Then, \(a - b = \frac{X}{S_1}\) is necessary, so \(S_1\) must be a divisor of \(X\). Then, \((a,b,S_2)\) must satisfy

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

For a fixed \(b\), \(a\) is uniquely determined, so it is sufficient to take the sum of \(\min(10,b)\) over all \(b\) such that \(S_1 < b \le N - \frac{X}{S_1}\), which can be done in \(\mathrm{O}(1)\) time.

If \(k \ge 3\)

Since \(a^k - b^k \equiv 0 \bmod (a - b)\), it is necessary that \((a-b)\) is a divisor of \(X\). Here, let \(s = a - b\); then \(a^2 - b^2 \le X\) is required, thus \(2sb + s^2 \le X\) is. Therefore, there are \(\mathrm{O}(X\log X)\) possible pairs of \((a,b)\).

Here, we can perform a dynamic programming to count \(S\) for each fixed pair \((a,b)\), since there are few \(k\) with \(a^k - b^k \le X\); meanwhile, we can prove that there are only at most one \(S\) satisfying the conditions, in fact.

Proof: if we have \(a^k - b^k > (b-1)(\sum_{i=0}^{k-1} a^i - b^i)\) for all \(k(\ge 1)\), then we can only greedily subtract \((a^k - b^k)\) from \(S\), so \(S\) is unique and the existence can be determined in an \(\mathrm{O}(\log X)\) time. The relation is true, as it can indeed be derived.

So, the case for \(k \ge 3\) can be solved in an \(\mathrm{O}(X\log^2 X)\) time. Since there are actually fewer \((a,b)\), and the integers \(k\) satisfying \(a^k - b^k \le X\) are fairly small.

Hence, the problem can be solved in a total of \(\mathrm{O}(X\log^2 X)\) time.