1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| class Solution {
unordered_map<int,vector<int>> cut{
{2, {2}},
{3, {3}},
{4, {2,2}},
{5, {5}},
{6, {2,3}},
{7, {7}},
{8,{2,2,2}},
{9, {3,3}}
};
int minLength(vector<int>& A) {
int res = A[5] + A[7] + A[2] / 3 + A[3] / 2;
if(A[2] % 3 == 2) res += 1 + (A[3] & 1);
else if(A[2] % 3 == 1) res += max(1, A[3] & 1);
else res += A[3] & 1;
return res;
}
string build(vector<int>& count) {
string res = "";
res += string(count[2] / 3, '8'); count[2] %= 3;
res += string(count[3] / 2, '9'); count[3] %= 2;
res += string(count[7], '7'); res += string(count[5], '5');
if(count[2] == 1 and count[3] == 1) {
res += "6";
count[2] -= 1, count[3] -= 1;
} else if(count[2] == 2 and count[3] == 1) {
res += "26";
count[2] -= 2;
count[3] -= 1;
} else if(count[2] == 2) {
res += "4";
count[2] -= 2;
}
if(count[2]) res += "2";
if(count[3]) res += "3";
sort(begin(res), end(res));
return res;
}
string helper(string& s, vector<int>& C) {
bool ok = false;
string str = "";
vector<array<int,4>> st;
st.push_back({0,0,0,0});
while(st.size()) {
auto [pos, fl, apply, x] = st.back(); st.pop_back();
if(ok) str.push_back('0' + x);
else {
for(auto& c : cut[apply]) {
C[c]++;
}
if(apply) {
if(++x == 10) continue;
else {
int napply = 1;
for(auto& c : cut[x]) {
if(C[c]) C[c]--, napply *= c;
}
st.push_back({pos,true,napply,x});
st.push_back({pos+1,true,0,-1});
}
} else {
if(pos == s.length()) {
int cnt = count(begin(C), end(C), 0);
if(cnt == 10) ok = true;
} else {
if(fl) {
int len = minLength(C);
if(s.length() - pos < len) continue;
str = string(s.length() - pos - len,'1') + build(C);
reverse(begin(str), end(str));
ok = true;
} else {
x = pos ? max(1, s[pos] - '0') : 0;
int napply = 1;
for(auto& c : cut[x]) {
if(C[c]) C[c]--, napply *= c;
}
st.push_back({pos,true,napply,x});
st.push_back({pos+1,x != (s[pos] - '0'),0,-1});
}
}
}
}
}
return str;
}
public:
string smallestNumber(string num, long long t) {
vector<int> count(10);
for(int i = 2; i <= 7 and i <= t; i++) {
while(t % i == 0) {
count[i]++; t /= i;
}
}
if(t != 1) return "-1";
if(minLength(count) > num.length()) return build(count);
num = "0" + num;
auto res = helper(num,count);
if(res.back() == '0') res.pop_back();
reverse(begin(res), end(res));
return res;
}
};
|
