Bzoj 1053(因数个数 + 打表)

Bzoj 1053
题意:见上。

本题就是一个打表的典型题。但是打表程序很有学问否则你离开考场都打不完表。
最容易想到$O(n \sqrt n)$的暴力,但是对于$2 \times 10^{9}$太慢了。
我们可以运用这个定理:

给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $n$ 的正约数的个数
根据乘法原理,$n$ 的正约数的个数为
$\prod_{i=1}^{k}(a_i+1)$

然后就可以打质数表进行分解因数。我们发现一个$2 \times 10^{9}$以内的数字不会有超过$12$个质因子,并且小素因子多一定比大素因子多要优,预处理出前$12$个质数即可。

打完表输出即可。打表直接打出反素数即可,反素数个数很少。

生成器 (500s+​ 能完成):

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
namespace flyinthesky {
LL pri[50] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};
void clean() {
}
int solve() {
clean();
freopen("1.out", "w", stdout);
LL maxn = 0ll;
for (LL i = 1ll; i <= 2000000000ll; ++i) {
LL tmp = 1ll, whw = i;
for (LL j = 0ll; j < 20ll; ++j) {
LL gg = 0ll, x = pri[j];
while (whw % x == 0ll) whw /= x, ++gg;
tmp *= (gg + 1ll);
}
if (tmp > maxn) printf("%lld ", i);
maxn = max(tmp, maxn);
}
printf("maxn=%lld\n", maxn);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

打表:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
namespace flyinthesky {
int atp[500] = {1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440, 83160, 110880, 166320, 221760, 277200, 332640, 498960, 554400, 665280, 720720, 1081080, 1441440, 2162160, 2882880, 3603600, 4324320, 6486480, 7207200, 8648640, 10810800, 14414400, 17297280, 21621600, 32432400, 36756720, 43243200, 61261200, 73513440, 110270160, 122522400, 147026880, 183783600, 245044800, 294053760, 367567200, 551350800, 698377680, 735134400, 1102701600, 1396755360, 2000001000};
void clean() {
}
int solve() {
clean();
int n; scanf("%d", &n);
for (int i = 1; ; i++) {
if (atp[i] > n && atp[i - 1] <= n) return printf("%d\n", atp[i - 1]);
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------