A题求救通过case80%
思路:维护一个变量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; }