P2821 变幻数

贪心

传送门

题目定义

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

1．如果 n 的位数多于 1 位（忽略前置的0），将 n 的各个位上的数相乘，乘积为 m。称 m 为 n 的子变幻数，n 称为 m 的父变幻数。求一个数的变幻数等于求其子变幻数。即求 n 的变幻数等于求 m 的变幻数。

2．如果 n 的位数只有一位，n 的变幻数即为它本身。
    
如求 679 的变幻数过程为：679 -> 378(=6*7*9) -> 168(=3*7*8) -> 48(=1*6*8) -> 32(=4*8) -> 6(=2*3)，所以 679 的变幻数为 6。

发现

如果要逆着求，可以先分解。于是就有了第一个思路：分解。

分解

以样例给的数先分解一波：枚举所有因数，再找最小的。

$48:1,2,3,4,6,8,12,16,24,48$

因为是每位相乘的得数，所以可以先排除：

$12,16,24,48$

剩下：

$2,3,4,6,8$ 要求最小的组合，那么一定不会用到 $1$。毕竟没啥用，还站着一位呢。而且剩下的数的组合，从高位到低位一定是字典序。

尝试

暴力

• $48=2\times3\times8$//毕竟不能出现两位数，能少位就少位

• $48=3\times4\times4$

• $48=6\times8$

显然，$3$ 最小

规律

通过上面的分解至少可以发现规律，尽量分成和最小的因数组。位数也尽量少。如果分解后让有高位数，就继续分解即可。最后再排次序即可。

正解

高精

需要高精存数与作除，但会发现个问题，上面说会分解，还有可能会很大的除因数，

所以一定还有玄机！！！

再分解

上面的分解最主要的就是分的尽量少，但是很有可能会出现特别情况。比如：最后出现$2\times2\times3\times4\times……$

所以并不是最优解！！！

那怎么做？既然是尽量少，还要<=$9$

结果

就可以从 $9$->$2$ 依次便利出结果，一定是最优解！！！

代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<queue>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
int x=9,a[1010],len,l=1;
vector<int>v;
int main(){
  char ch=getchar();
  for(;!isdigit(ch);ch=getchar());
  for(;isdigit(ch);ch=getchar())a[++len]=ch-'0';
  while(x>=2){
    int y=0;
    for(int i=1;i<=len;i++){
      y=y*10+a[i];
      y%=x;
    }
    if(y)x--;
    else{
      v.push_back(x);
      for(int i=1;i<=len;i++){
        y=y*10+a[i];
        a[i]=y/x;y%=x;
      }if(a[l]==0)l++;
    }
  }if(len!=l)puts("There is no such number!");
  else for(int i=v.size()-1;i>=0;i--)cout<<v[i];
  return 0;
}