この問題で最も重要な事実は、「\(10^{18}\) 未満の等差数はそう多くない」ということです。まずはこのことを見積もりましょう。
等差数のもとになる等差数列 (例えば \((2,4,6,8) \rightarrow 2468\)) の候補を考えます。 等差数列が満たすべき必要条件は以下です。

• 初項が \(1\) 以上 \(9\) 以下である。
• 公差が \(-9\) 以上 \(8\) 以下である。
• 数列の長さは \(1\) 以上 \(18\) 以下である。

(長さ \(1\) の数列を重複して数えたとしても、) この条件を満たす数列は \(9 \times 18 \times 18 = 2916\) 個以下であることがわかります。 ただし、この条件を満たしていても、 \((7,1,-5)\) のような数列は等差数のもととはなりません。追加で以下の条件が必要です。

• 第 \(2\) 項以降が全て \(0\) 以上 \(9\) 以下である。

上に挙げた \(4\) つの条件全てを満たせば十分です。あとは、これをもとに等差数を全列挙し、 \(X\) 以上であるものの中で最小のものを出力すればよいです。なお、 \(X=10^{17}\) である場合、答えは \(111111111111111111\) (\(1\) が \(18\) 個並んだ数) なので、 \(10^{18}\) 以上の等差数は考慮に入れる必要がありません。

この解法は、等差数の列挙が定数時間であるため、定数時間で動作します。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

set<long long> gen_tosasu(){
  set<long long> res;
  for(int fir=1;fir<=9;fir++){
    for(int d=-9;d<=8;d++){
      string s;
      int dg=fir;
      for(int i=0;i<18;i++){
        s.push_back(dg+'0');
        res.insert(stoll(s));
        dg+=d;
        if(!(0<=dg && dg<=9)){break;}
      }
    }
  }
  return res;
}

int main(){
  long long x;
  cin >> x;
  set<long long> st=gen_tosasu();
  cout << (*st.lower_bound(x)) << '\n';
  return 0;
}