F - Palindromic Expression （abc363）

题意：给你一个整数 N 请打印一个满足以下所有条件的字符串 S 。如果不存在这样的字符串，则打印 -1。

S 是长度在 1 和 1000 之间的字符串，由字符 1、2、3、4、5、6、7、8、9 和 *(乘号)组成。S 是一个回文字符。S 的第一个字符是一位数字。将 S 作为公式求值时，其值等于 N 。

分析：可以每次递归用来搜索满足条件的数列，如果搜到回文数了，就将前面的数列一并输出，还有反转后的数列乘积表达式，如果不是回文数，继续递归分解n。在判断回文数时，不能包含0.

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll v,a[60],n;
ll f(ll x){
	ll s=0;
	while(x){
		if(x%10==0){
			return s=9e18;
		}
		s=s*10+x%10;
		x/=10;
	}
	return s;
}
void dfs(ll k,ll n){
	if(v==1)return;
	if(f(n)==n){
		a[k]=n;
		v=1;
		for(ll i=1;i<k;i++){
			printf("%lld*",a[i]);
		}
		printf("%lld",a[k]);
		for(ll i=k-1;i>=1;i--){
			printf("*%lld",f(a[i]));
		}
	}
	for(ll i=2;i*i<=n;i++){
		ll j=f(i);
		if(n%i!=0||n/i%j!=0)continue;
		a[k]=i;
		dfs(k+1,n/i/j);
	}
}
int main(){
	scanf("%lld",&n);
	dfs(1,n); 
	if(!v)cout<<"-1"<<endl;
	return 0;
}