[ABC363] F - Palindromic Expression

[Q] F - Palindromic Expression

気づけばなんてことはなかった！
考察
0. 素因数分解しちゃだめ！もっとシンプル。
1. A * B * 回文式 * B' * A' が回答の型になることを考える。
2. Nが回文なら回文式だけ出力して終わり。そうでない場合Aを求める。
3. Aの上限は√Nまで。O(√N)で全然間に合う。
4. AとA'が定まったらN->N/A/A'して、Nが小さくなる。
5. 新しいNが回文なら答え。そうでないならBを求める。
6. 掘り下げるごとにNが回文かどうか確かめて、回文式を得られたら解答とすればいい。
7. 最後まで見つからなければ-1

実装

int main() {
  cincout();
  
  ll N;
  cin >> N;
  // N = A * B * parindrome * B * A

  // 数が0を含まない回文かどうか
  auto isParindrome = [](ll n)->bool{
    string s = to_string(n);
    rep(i, (s.size() + 1) / 2){
      if (s[i] == '0') return false;
      if (s[i] != s[s.size() - 1 - i]) return false;
    }
    return true;
  };

  // 数が0を含まないかどうか 
  auto isValid = [](ll n)->bool{
    string s = to_string(n);
    for(auto c: s) if (c == '0') return false;
    return true;
  };

  // 答えの出力。rev*n*(^rev)のつもり
  auto pans=[](vector<ll>&rev, ll n){
    vector<string> v;
    for(auto x : rev) v.push_back(to_string(x));
    if (n > 0) v.push_back(to_string(n));
    rrep(i, rev.size()){
      string s = to_string(rev[i]);
      reverse(all(s));
      v.push_back(s);
    }
    rep(i, v.size()){
      cout << v[i] << "*\n"[i == v.size() - 1];
    }
  };

  // 数を逆さにする
  auto getRev=[&](ll n)->ll{
    string s = to_string(n);
    reverse(all(s));
    return stoll(s);
  };

  // 答えが見つかったらtrue
  function<bool(ll, vector<ll>&)> dfs = [&](ll n, vector<ll>&revlist)->bool{
    if (isParindrome(n)){
      pans(revlist, n);
      return true;
    }
    for(ll i = 2; i * i <= n; ++i){
      if (!isValid(i)) continue;
      if (n % i != 0) continue;
      ll rev = getRev(i);
      if ((n / i) % rev != 0) continue;
      revlist.push_back(i);
      if (dfs(n / i / rev, revlist)) return true;
      revlist.pop_back();
    }
    return false;
  };

  vector<ll> revlist;
  if (dfs(N, revlist)) return 0;
  cout << -1 << endl;
}

https://atcoder.jp/contests/abc363/submissions/55827501