题目： UVa1642
solution
因为要求一个最优的子序列，可以想到枚举这个子序列的右端点\(j\)。 那么怎么快速算出左端点\(i\)的答案呢？
枚举每一个左端点，如果能知道这个子序列所有元素的\(gcd\)值就好了。
先考虑这样一个序列\(5,8,8,6,2\)，假设现在\(j=4\),可以算出所有子序列对应的\(gcd\)。 1. \(i=1\), \(gcd(a_1,a_2,a_3,a_4)=1\) 2. \(i=2\), \(gcd(a_2,a_3,a_4)=2\) 3. \(i=3\), \(gcd(a_3,a_4)=2\) 4. \(i=4\), \(gcd(a_4)=6\)
注意到不同子序列的\(gcd\)值有可能是相等的，事实上\(gcd\)值的种类最多不会超过\(\log_2 a_j\)个，因为\(a_j\)的约数个数一定不多于\(\log_2 a_j\)。
上表从下向上看，每次增加一个元素的时候，\(gcd\)值是不变或者减小的，而且变小时一定会变成\(a_j\)的一个约数。所以就维护每个左端点对应的区间\(gcd\)值(即\(gcd(a[i],a[i+1],...,a[j])\))，增加一个元素(即\(j\) -> \(j+1\))时，更新加上该元素后的区间\(gcd\)值就可以。
知道了当前每个左端点对应的\(gcd\)，区间长度也是已知的，就可以计算答案了，对于每个区间的结果取一个最大值。
但是直接这样做复杂度是不对的，\(O(n^2log
n)\)显然过不了。那怎么办呢。 我们可以发现，如果两个左端点的\(gcd\)相等，那么\(i\)更小的一定会更优，所以直接把劣的删除，对后面不造成影响。这样一来每次要枚举的\(i\)就和\(gcd\)的个数有关，复杂度是\(O(nlog^2 n)\)，可以通过本题。
code
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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll n, a[N];
vector<pair<int, ll> > v;
ll read() {
ll w = 0; char ch = getchar();
while(ch > '9' || ch < '0') ch = getchar();
while(ch >= '0' && ch <= '9') {
w = w * 10 + ch - 48;
ch = getchar();
}
return w;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
ll T = read();
while(T--) {
ll ans = 0; v.clear();
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int j = 1; j <= n; j++) {
v.push_back({j, a[j]});
for(int i = v.size() - 2; i >=0; i--) {
v[i].second = gcd(v[i].second, a[j]);
if(v[i].second == v[i + 1].second) v.erase(v.begin() + i + 1);
}
for(int i = 0; i < v.size(); i++) {
ans = max(ans, (j - v[i].first + 1) * (v[i].second));
}
}
printf("%lld\n", ans);
}
return 0;
}
|