[ABC363F] Palindromic Expression 讲解

zrl123456 · 2024-07-22 17:59:47 · 题解

[ABC363F] Palindromic Expression

题目考察：记忆化，搜索，数学。
题目简述：
给你一个数 n，求一个满足以下条件的字符串 s，若没有一个字符串满足条件，输出 -1：

数据范围：

• 1\le n\le 10^{12}

  考虑暴力搜索。
  对于每一个 n，我们考虑找到一对 n 的回文因数 a,b（在这里定义回文因数为：若 a,b 为 n 的因数，且 a,b 互为回文，则称 a,b 是一对回文因数），同时 a,b 还不能包含 0，那么我们将 n 除以 a 和 b，继续往下搜索。
  但这样还不行，因为对于 n=48，可以经过 2*2*3*2*2 搜索到 3，也可以经过 4*3*4 搜索到 3，所以我们要用一个 map 来记忆化，也可以用 unordered_map 来省去一个 \log。

最终时间复杂度为 \Theta(\sqrt n\log n)。
代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define repe(i,x,y) for(i=x;i<=(y);++i) 
#define endl '\n'
#define INF 1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
#define sstr stringstream 
#define all(x) x.begin(),x.end()
#define mcy(a,b) memcpy(a,b,sizeof(b))
using namespace std;
map<int,string>mp;
inl int rvs(int n){
    reg int x=n,y=0;
    while(x){
        y=(y<<1)+(y<<3)+x%10;
        x/=10;
    }
    return y;
}
inl bool check0(int n){
    reg int x=n;
    while(x){
        if(!(x%10)) return 0;
        x/=10;
    }
    return 1;
}
inl bool check(int n){
    return n==rvs(n);
}
inl string getans(int n){
    if(mp.count(n)) return mp[n];
    if(check(n)&&check0(n)) return mp[n]=to_string(n);
    rep(i,2,sqrt(n)){
        reg int rvsi=rvs(i);
        if(n%(i*rvsi)||!check0(i)||!check0(rvsi)) continue;
        reg string s=getans(n/i/rvsi);
        if(s=="-1") continue;
        return mp[n]=to_string(i)+"*"+s+"*"+to_string(rvsi);
    }
    return "-1";
}
signed main(){
    fst;
    reg int n;
    cin>>n;
    cout<<getans(n);
    return 0;
}