本文共 1918 字，大约阅读时间需要 6 分钟。

$$变幻数$$

题目链接：

题目

给定一个十进制正整数$n$，它的递归变幻数定义如下：

1. 如果$n$的位数多于$1$位（忽略前置的$0$），将$n$的各个位上的数相乘，乘积为$m$。称$m$为$n$的子变幻数，$n$称为$m$的父变幻数。求一个数的变幻数等于求其子变幻数。即求$n$的变幻数等于求$m$的变幻数。
2. 如果$n$的位数只有一位，$n$的变幻数即为它本身。 如求$679$的变幻数过程为：$679->378(=6\ast 7\ast 9)->168(=3\ast 7\ast 8)->48(=1\ast 6\ast 8)->32(=4\ast 8)->6(=2\ast 3)$，所以$679$的变幻数为$6$。

现在的问题是给定一个子变幻数$k$，问$k$的父变幻数最小是多少？ 如：$k=18$，则$k$的父变幻数可以是$29$，也可以是$92$。但最小为$29$。

输入

一个子变幻数$k($位数小于$1000)$。

输出

$k$的最小父变幻数。 当不存在父变幻数时请输出$“Thereisnosuchnumber!”$，输出结果不含引号。

样例输入

48

样例输出

68

思路

这道题是一道贪心题。

题目告诉我们子变幻数就是父变幻数的各个位的乘积，那么就是说如果我们把子变幻数分解成一些大于$0$小于$10$的数，然后按各种方法排列起来的话，组成的数都是子变幻数的父变幻数。

有一点要注意的是要用高精除，因为子变幻数可以有1000位，父变幻数就更不用说了。

代码

#include
   
    #include
    
     using namespace std;int a[10], num[1001], k, an[1001];char b[1001];int main() {   	scanf("%s", &b);//读入	for (int i = 0; i < strlen(b); i++) {   		num[++k] = b[i] - 48;//转换成数字	}		int i = 9;//初始化	while (i >= 2) {   //分解除每一个数字（以最优的方法）		int now = 0;		for (int j = 1; j <= k; j++) {   //高精除			now = now * 10 + num[j];			an[j] = now / i;			now %= i;		}				if (!now) {   //判断能否整除			int fr = 1;			a[i]++;//可以被整除，计入答案			while (!an[fr]) fr++;			for (int j = fr; j <= k; j++)				num[j - fr + 1] = an[j];			k = k - fr + 1;		}		else i--;//不能整除	}		if (k > 1) printf("There is no such number!");//不存在父变幻数		else {   			for (int i = 2; i <= 9; i++)				for (int j = 1; j <= a[i]; j++)					printf("%d", i);//输出答案		}		return 0;}