ACGO欢乐赛#42题解

Solution

观察样例，发现 $4!=3!\times2!\times2!$，因此考虑拆分。

• 对于 $x=0/1$，无需考虑。
• 对于 $x=2$，考虑拆分为 $\{2\}$。
• 对于 $x=3$，考虑拆分为 $\{3\}$。
• 对于 $x=4$，考虑拆分为 $\{3,2,2\}$。
• 对于 $x=5$，考虑拆分为 $\{5\}$。
• 对于 $x=6$，考虑拆分为 $\{5,3\}$。
• 对于 $x=7$，考虑拆分为 $\{7\}$。
• 对于 $x=8$，考虑拆分为 $\{7,2,2,2\}$。
• 对于 $x=9$，考虑拆分为 $\{7,3,3,2\}$。

我们发现一个神奇的现象，所有数都被拆成了质数，而之后我们只需要把所有数排个序就行了。

Code

#include <bits/stdc++.h>
#include <cstdio>
#define int long long
#define ull unsigned long long
#define mod 988444333
#define MOD 1000000007
#define in(x,y,z) x>=y&&x<=z
using namespace std;
const int N = 2e6 + 5;
int a [N];
inline int read ()
{
	int x = 0;
	bool f = 1;
	char c = getchar ();
	while (c < '0' || c > '9') f = (c == '-' ? !f : f),c = getchar ();
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar ();
	return (f ? x : -x);
}
inline void write (int x)
{
	if (x < 0) putchar ('-'),x = -x;
	if (x > 9) write (x / 10);
	putchar (x % 10 + '0');
	return ;
}
bool cmp (int x,int y) {return x >= y;}
signed main ()
{
	int x;
	cin >> x;
	vector <int> ans;
	map <int,vector <int> > mp;
	mp [0] = {};
	mp [1] = {};
	mp [2] = {2};
	mp [3] = {3};
	mp [4] = {3,2,2};
	mp [5] = {5};
	mp [6] = {5,3};
	mp [7] = {7};
	mp [8] = {7,2,2,2};
	mp [9] = {7,3,3,2};
	while (x)
	{
		int d = x % 10;
		vector <int> v = mp [d];
		for (int &i : v) ans.push_back (i);
		x /= 10;
	}
	sort (ans.begin (),ans.end (),cmp);
	for (int &i : ans) cout << i;
	return 0;
}