题意:给你一个整数 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;
}