c++ - 无法理解使用此 map<> 方法背后的证明

Question

Drazil is playing a math game with Varda.

Let's define for positive integer x as a product of factorials of its digits. For example, f(135) = 1! * 3! * 5! = 720.

First, they choose a decimal number a consisting of n digits that contains at least one digit larger than 1. This number may possibly start with leading zeroes. Then they should find maximum positive number x satisfying following two conditions:

1. x doesn't contain neither digit 0 nor digit 1.

2. = f(x) = f(a)

Help friends find such number.

Input The first line contains an integer n (1 ≤ n ≤ 15) — the number of digits in a.

The second line contains n digits of a. There is at least one digit in a that is larger than 1. Number a may possibly contain leading zeroes.

Output Output a maximum possible integer satisfying the conditions above. There should be no zeroes and ones in this number decimal representation.

Examples
input
4
1234
output
33222

input
3
555
output
555

这是解决方案，

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

int main()
{
  map<char, string> mp;

  mp['0'] = mp['1'] = "";
  mp['2'] = "2";
  mp['3'] = "3";
  mp['4'] = "223";
  mp['5'] = "5";
  mp['6'] = "35";
  mp['7'] = "7";
  mp['8'] = "2227";
  mp['9'] = "2337";

  int n;
  string str;

  cin>>n>>str;

  string res;

  for(int i = 0; i < str.size(); ++i)
    res += mp[str[i]];

  sort(res.rbegin(), res.rend());

  cout<<res;

  return 0;
}

我想如果有人解释为什么数字被转换成其他形式的数字而不是仅仅用某种方法来计算数字的原因......遗憾的是蛮力会在这个问题中给出 TLE(超出时间限制) 15 位数字的原因，所以对于蛮力来说这是一个很大的数字，所以我衷心希望有人能解释下面的“证明”，因为我知道这些数字可以转换为这些数字的理论是什么，例如 4 到 223 和东西。 提前致谢。

Picture: What the proof says

Answer 1

这些转换背后的理论如下(我以 4 为例):

4! = 3! * 2! * 2!

较长的数字序列总是会比较短的序列产生更大的数字(至少对于正整数而言)。因此，此代码会尽可能产生更长的序列。通过上面的例子我们得到:

4! = 3! * 4

我们不能减少 3!更进一步，因为 3 是质数。另一方面，4 就是 2²:

4 = 2² = 2! * 2!

因此，我们找到了数字序列中 4 的最佳替换为“322”。这可以对所有数字完成，但质数不可因式分解，因此始终是它们自身可用的最佳替代品。

而且由于我们使用质因数分解这一事实，我们还知道我们拥有唯一(也是最长可能)的数字串可以替换某个数字。