思路:维护一个变量top表示当前连续区间内符合条件（是区间内其他数的公约数）的数,若加上第i个数也是合法的总共有俩种情况
1.ai是top的约数，显然成立我让top变成ai
2.top是ai的约数，显然成立
len数组维护当前的最大长度
code:
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 6e6;
int n,a[MAXN],len[MAXN],top,ans,res;
int main()
{
cin >> n;
for(int i = 1;i <= n;i += 1)
cin >> a[i];
top = a[1];
len[1] = 1;
ans = 1;
res = 1;
for(int i = 2;i <= n;i += 1)
{
if(a[i] % top == 0)
{
len[i] = len[i - 1] + 1;
if(ans < len[i])
{
ans = len[i];
res = 0;
}
if(ans == len[i])res++;
continue;
}
if(top % a[i] == 0)
{
top = a[i];
len[i] = len[i - 1] + 1;
if(ans < len[i])
{
ans = len[i];
res = 0;
}
if(ans == len[i])res++;
continue;
}
len[i] = 1;
top = a[i];
}
cout << res << endl;
return 0;
} 
全部评论
(1) 回帖