题意
【题目描述】
小 H 是个善于思考的学生，现在她又在思考一个有关序列的问题。
她的面前浮现出一个长度为 n的序列{ai}，她想找出一段区间L, R。
这个特殊区间满足，存在一个 k(L <= k <= R)，并且对于任意的 i(L <= i <= R)，ai 都能
被 ak 整除。这样的一个特殊区间 [L, R]价值为 R - L。
小 H 想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些
区间又分别是哪些呢？你能帮助她吧。
【输入格式】
第一行，一个整数 n.
第二行，n个整数，代表 ai.
【输出格式】
第一行两个整数，num和 val,表示价值最大的特殊区间的个数以及最大价值。
第二行 num 个整数，按升序输出每个价值最大的特殊区间的 L.
【样例输入 1】
5
4 6 9 3 6
【样例输出 1】
1 3
2
【样例输入 2】
5
2 3 5 7 11
【样例输出 2】
5 0
1 2 3 4 5
【数据范围】
30%: 1 <= n <= 30 , 1 <= ai <= 32.
60%: 1 <= n <= 3000 , 1 <= ai <= 1024.
80%: 1 <= n <= 300000 , 1 <= ai <= 1048576.
100%: 1 <= n <= 500000 , 1 <= ai < 2 ^ 31.
分析
等下再具体的打...
RMQ的思想， 求区间gcd和最小值， 二分找答案
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 500000+9;
inline int gcd(int x, int y) {return !y ? x : gcd(y, x%y);}
int n;
int f[N][20], g[N][20];
void init() {
for(int k = 1; (1<<k) <= n; k++) {
for(int i = 1; i+(1<<k)-1 <= n; i++) {
f[i][k] = min(f[i][k-1], f[i+(1<<(k-1))][k-1]);
g[i][k] = gcd(g[i][k-1], g[i+(1<<(k-1))][k-1]);
}
}
}
int RMQ_gcd(int l, int r) {
int m = r - l + 1;
int k = 0;
while(1<<k <= m) k++;
k--;
return gcd(g[l][k], g[r-(1<<k)+1][k]);
}
int RMQ(int l, int r) {
int m = r - l + 1;
int k = 0;
while(1<<(k+1) <= m) k++;
return min(f[l][k], f[r-(1<<k)+1][k]);
}
int num;
int ans[N], tot;
int check(int Len) {
int r, is = 0;
for(int l = 1; l <= n && l + Len - 1 <= n; l++) {
r = l+Len-1;
if(RMQ(l, r) == RMQ_gcd(l, r)) {
if(is == 0) tot = 0;
is = 1;
ans[++tot] = l;
}
}
return is;
}
int main() {
// freopen("pair.in", "r", stdin);
// freopen("pair.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &f[i][0]), g[i][0] = f[i][0];
init();
int l = 1, r = n, mid, Len;
while(l <= r) {//左闭右闭
mid = (l+r)>>1;
if(check(mid)) {
Len = mid;
l = mid+1;
num = tot;
} else {
r = mid - 1;
}
}
printf("%d %d\n", num, Len - 1);
for(int i = 1; i <= tot; i++) printf("%d ",ans[i]);
}
/*
7
6 3 9 18 4 8 2
*/