题目
题目大意
输入一个\(n\)(\(n ≤ 100000\))个元素的正整数序列\(a_1, a_2, \cdots , a_n\)(\(1 ≤ a_i ≤ 10^{12}\)), 求一个连续子序列,
使得该序列中所有元素的最大公约数与序列长度的乘积最大。例如, \(5\)个元素的序列\(30, 60, 20, 20, 20\)的最优解为\(\{60, 20, 20, 20\}\), 乘积为\(4(60, (20, (20, (20, 20)))) = 80\)。
题解
对于\(n + 1\)个数与\(n\)个数的最大公约数要么相等,
要么减小并且减小至少一半(至少少了一个因子)。因此所有子串最大公约数的总种类数最多只有\(n \lg a\)(\(a\)为最大数大小)个。我们枚举每个点计算以这个点为结束点的所有后缀,
利用DP的思想通过前一次计算的最多\(\lg
a\)个最大公约数计算出此时也是最多\(\lg
a'\)个最大公约数。
代码
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 <cstdio>
#include <cstring>
#include <algorithm>
long long arr[100010], gcd[100010][100];
int length[100010][100];
int T, n;
inline long long GreatestCommonDivisor(const long long&, const long long&);
int main(int argc, char const *argv[]) {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (register int i(0); i < n; ++i) {
scanf("%lld", &arr[i]);
}
register long long ans(0LL);
register int countt, previous(0);
for (register int i(0); i < n; ++i) {
countt = 0;
gcd[i][countt] = arr[i],
length[i][countt] = 1;
ans = std::max(ans, arr[i]);
++countt;
for (register int j(0); j < previous; ++j) {
gcd[i][countt] = GreatestCommonDivisor(arr[i], gcd[i - 1][j]);
length[i][countt] = length[i - 1][j] + 1;
ans = std::max(ans, gcd[i][countt] * length[i][countt]);
if (gcd[i][countt] == gcd[i][countt - 1]) {
length[i][countt - 1] = length[i][countt];
} else {
++countt;
}
}
previous = countt;
}
printf("%lld\n", ans);
}
return 0;
}
inline long long GreatestCommonDivisor(const long long &a, const long long &b) {
return b ? GreatestCommonDivisor(b, a % b) : a;
}
|