题解 P2821 【变幻数】
kradcigam
2020-03-17 10:27:22
# 前言
这道题还真是一道好题。
# 正文
## 分析
首先，我们想一想，一个子变幻数要满足什么条件。
**有最大质因子不能超过 $9$ 中的。**
然后，发现 $k$ 的父变幻数最小就 $k$ 从 $9$ 到 $2$ 去分解 $k$，然后存起来，最后再反着输出。
为什么？
1. 为了 $k$ 的父变幻数最小，我们第 $1$ 个要保证位数尽量的少。
2. 在位数尽量少的前提下，我们要让数尽量小、
```cpp
#include <bits/stdc++.h>
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;
}
```
# 后记
如果有问题，大家可以在评论区写下来，让这篇题解更加完善。