提出 #55825147

---

ソースコード 拡げる

// https://codeforces.com/blog/entry/125435
#ifdef MAXWELL_LOCAL_DEBUG
#include "debug/debug_template.cpp"
#else
#define debug(...)
#define debugArr(arr, n)
#endif

#define dbg debug()

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using vi = vector<int>;

using tii = tuple<int,int,int>;
// auto [a,b,c] = ...
// .insert({a,b,c})

const int oo = (int)1e9 + 5; //INF to INT
const ll OO = 0x3f3f3f3f3f3f3f3fLL; //INF to LL
   
ll rev(ll x) {
    string s = to_string(x);
    reverse(s.begin(), s.end());
    ll ans = 0;
    for(auto &p : s) {
        ans = 10 * ans + (p - '0');
    }
    return ans;
}

bool zero(ll x) {
    while(x > 0) {
        if(x % 10 == 0) {
            return true;
        }
        x /= 10;
    }
    return false;
}

int palin(ll x) {
    return x == rev(x);
}


// when using pairs
struct custom_hash {
    inline size_t operator ()(const pair<ll, ll> & a) const {
        return (a.first << 6) ^ (a.first >> 2) ^ 2038074743 ^ a.second;
    }
};

vector<ll> factors;

//map<int, map<ll, bool>> tb;

unordered_map<pair<ll, ll>, bool, custom_hash> tb;
//unordered_map<ull, bool> tb;

bool dp(int i, ll val) {

    if(i == -2 && val == 1) {
        return true;
    }

    if(i < 0) {
        return false;
    }

    if(tb.find(make_pair(i, val)) != tb.end()) {
        return tb[make_pair(i, val)];
    }

    //debug(i, val);

    auto& ans = tb[make_pair(i, val)];

    for(auto &d : factors) {
        if(d > val) break;
        if(val % d || zero(d)) continue;
        auto r = rev(d);
        if((val / d) % r) continue;

        auto sz = (int)to_string(d).size();

        ans |= dp(i - sz - 1, val / d / r);
    }

    return ans;

}

void solve(ll N, int INIT) { 
    
    bool odd = false;
    bool ans = false;

    ll start = -1;

    for(auto &d : factors) {
        if(!zero(d)) {
            auto sz = (int)to_string(d).size();
            if(palin(d) && dp(INIT - sz - 1, N / d)) {
                ans = true;
                odd = true;
                start = d;
                debug("mid", d);
                break;
            } 
            auto r = rev(d);
            if((N / d) % r == 0 && dp(INIT - sz - 1, N / d / r)) {
                ans = true;
                start = d;
                debug("mid", d, r);
                break;
            }
        }
    }

    if(!ans) {
        return;
    }

    ll cur = INIT - (int)to_string(start).size() - 1;
    
    vector<ll> p;

    if(odd) {
        N /= start;
    } else {
        N /= start;
        N /= rev(start);
    }

    //p.push_back(start);

    debug(p, N);

    while(cur != -2 || N != 1) {
        debug(cur, N, p);
        for(auto &d : factors) {
            int sz = (int)to_string(d).size();
            if(zero(d) || N % d) continue;

            ll r = rev(d);

            if((N / d) % r == 0 && dp(cur - sz - 1, N / d / r)) {
                debug("pega", d);
                cur = cur - sz - 1;
                N /= d; N /= r;
                p.push_back(d);
                //exit(0);
                break;
            }
        }
    }

    debug(odd);
    debug(p);

    vector<ll> r;

    for(auto &x : p) {
        r.push_back(rev(x));
    }

    reverse(r.begin(), r.end());

    vector<ll> mid = { start };

    if(!odd) {
        mid.push_back(rev(*mid.begin()));
    }

    debug(p, mid, r);

    vector<ll> ans_final;

    for(auto &x : p) ans_final.push_back(x);
    for(auto &x : mid) ans_final.push_back(x);
    for(auto &x : r) ans_final.push_back(x);
    
    for(int i = 0; i < (int)ans_final.size(); i++) {
        if(i) cout << "*";
        cout << ans_final[i];
    }

    cout << "\n";

    exit(0);

}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll N;
    cin >> N;

    for(ll i = 1; 1LL * i * i <= N; i++) {
        if(N % i != 0) continue;
        factors.push_back(i);
        if(N / i != i) {
            factors.push_back(N / i);
        }
    }

    sort(factors.begin(), factors.end());

    tb.reserve(1e5);

    debug(factors);

    solve(N, 80);
    solve(N, 80 + 1);

    cout << "-1\n";

}

提出情報

ジャッジ結果