ARC34B

問題概要

正整数\(n\)に対し、\(n\)の十進表記における各桁の和を\(f(n)\)で表す。正整数\(N\)が与えられた時に、\(x+f(x)=N\)を満たす正整数\(x\)を全て求めよ。

制約

• \(1≤N≤\)10¹⁸

考えたこと

• Nの制約が 10¹⁸ ということもあり、\(O(N)\)のアルゴリズムではTLEしてしまう。
• \(f(x)\) は桁和であるため、\(f(x)\) の最大値を考えてみると、\(9 \times 17 < 200\) とわかる。
• そのため、\(N-200 <= x < N\)として\(f(x) = N-x\)というこの等式を満たす\(x\)の個数とその値を求めればよいという問題に帰着できる。

書いたコード

#include <bits/stdc++.h>
using namespace std;

long long f(long long x) {
  string X = to_string(x);
  long long sum = 0;
  for(int i = 0; i < X.size(); ++i) {
    sum += (long long)(X[i] - '0');
  }
  return sum;
}

int main() {
  long long N; cin >> N;
  long long cnt = 0;
  vector<long long> v;
  for(long long x = N; x >= N - 200; x--) {
    if(f(x) == N-x) {
      cnt++;
      v.push_back(x);
    }
  }
  cout << cnt << endl;
  if(cnt != 0) {
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); ++i) {
      cout << v[i] << endl;
    }
  }
  return 0;
}