下文中提到的数字都不包含 0，注意把含 0 的数字特判掉。
反转指各个数位倒过来，比如 114514 反转过后就是 415411。
注意到，答案一定是这样：数列 \(a\) 的各个数字相乘，乘以一个回文，再把数列 \(a\) 倒过来，每个数反转，再相乘。
比如：2*57*184481*75*2，其中的数列 \(a\) 就是：2 57，中间的回文就是 184481。
搜索，先搜两边，把一个数和把它反转后的数拼成一对，如果 \(n \mod (i\times i') =0\)（\(i'\) 是 \(i\) 反转的数），那么 \(i\) 就可以被加进数列里，然后把 \(n\) 除以 \(i\times i'\) 继续搜索，搜索出一个合法解就退出。
由于合法的对数不会太多，所以可以预处理可能出现在答案里的对，然后暴力搜索。
时间复杂度：\(O(能过)\)。
点击开 D
const int N=1099;
ll n,a[N]={},fan[1000099]={};
bool nozero(ll n) {
while(n) {
while(n%10==0)
return false;
n/=10;
}
return true;
}
bool ishui(ll n) {
if(!nozero(n))
return false;
int a[20]={},i,j;
while(n)
a[++a[0]]=n%10,
n/=10;
for(i=1,j=a[0];i<j;++i,--j)
if(a[i]!=a[j])
return false;
return true;
}
ll turn(ll n) {
ll ans=0;
while(n)
ans=ans*10+n%10,
n/=10;
return ans;
}
ll g[1000099]={},leftans=0;
bool solve(ll n) {
if(ishui(n)) {
leftans=n;
return true;
}
for(int i=2;i<=g[0]&&g[i]*fan[g[i]]<=n;++i)
if(n%(g[i]*fan[g[i]])==0) {
if(solve(n/(g[i]*fan[g[i]]))) {
a[++a[0]]=g[i];
return true;
}
}
return false;
}
int main()
{
ll i;
read(n);
for(i=1;i<=1e6;++i) {
fan[i]=turn(i);
if(i<=fan[i]&&n%i==0&&(n/i)%fan[i]==0&&nozero(i))
g[++g[0]]=i;
}
if(solve(n)) {
for(i=1;i<=a[0];++i)
printf("%lld*",a[i]);
printf("%lld",leftans);
for(i=a[0];i;--i)
printf("*%lld",fan[a[i]]);
printf("\n");
} else printf("-1\n");
return 0;
}