找到第\(n\) \( (1 \le n \le 5842)\) 个只有2，3，5或7质因子的数。
链接： https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=384
###题解
####解法1
有点暴力。。。 用STL set和vector来枚举所有符合条件的数。用long long来防止爆int和栈。
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
| #include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int t[] = { 2, 3, 5, 7};
set<ll> s;
int main(void) {
s.insert(1);
set<ll>::iterator i = s.begin();
while(s.size() < 6600) {
for (int j = 0; j < 4; j++)
s.insert((*i)*t[j]);
i++;
}
vector<ll> v(s.begin(), s.end());
int n;
string s;
while (cin >> n) {
if (n == 0) break;
if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13) s = "th";
else if (n % 10 == 1) s = "st";
else if (n % 10 == 2) s = "nd";
else if (n % 10 == 3) s = "rd";
else s = "th";
cout << "The " << n << s << " humble number is " << v[n-1] << ".\n";
}
return 0;
}
|
####解法2
我们有：
| 数组 | 描述 |
|---|
| a | 质因子使用的次数，用来生成下一个数 |
| num | 保存4个质因子生成的数， 找到最小的填入ans数组中 |
| ans | 打表 |
每一个humble number \(a\)，一定存在一个小于\(a\)的humble number \(b\) 使得\(\lbrace a = kb, k \in \lbrace 2, 3, 5, 7\rbrace \rbrace\)
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
| #include<iostream>
#include<algorithm>
#include<string>
#define maxn 5842+5
using namespace std;
const int t[] = { 2, 3, 5, 7 };
int a[4] = {1, 1, 1, 1}, num[4], n, ans[maxn];
string s;
int find_min() {
int Min = num[0];
for (int j = 1; j < 4; j++) {
if (Min > num[j]) { Min = num[j]; }
}
return Min;
}
int main(void) {
int index = 2;
ans[1] = 1;
while(index < maxn) {
for (int i = 0; i < 4; i++) num[i] = ans[a[i]]*t[i];
ans[index] = find_min();
for (int i = 0; i < 4; i++) {
if (ans[index] == num[i]) a[i]++;
}
index++;
}
while (cin >> n) {
if (n == 0) break;
if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13) s = "th";
else if (n % 10 == 1) s = "st";
else if (n % 10 == 2) s = "nd";
else if (n % 10 == 3) s = "rd";
else s = "th";
cout << "The " << n << s << " humble number is " << ans[n] << ".\n";
}
return 0;
}
|