Забавная игра
Вы с друзьями играете в следующую игру. Друзья пишут на доске подряд N натуральных чисел. Ваша задача — найти как можно больше подряд идущих чисел, которые бы делились на одно и то же число, большее 1. Так как вручную искать ответ сложно, вы решили написать программу, которая сделает работу за вас.
Входные данные
В первой строке входных данных задано число N(1 ≤ N ≤ 100000). Во второй строке записано через пробел N целых чисел A1...AN(1 ≤ Ai ≤ 1000, 1 ≤ i ≤ N). Это те самые числа, которые написали ваши друзья. Они даны в том же порядке, в котором они расположены на доске.
Выходные данные
Ваша программа должна вывести одно целое число — наибольшее количество подряд идущих чисел заданной последовательности, которые бы делились на одно и то же натуральное число, большее 1.
Примеры
Ввод
3
6 10 15
Вывод
2
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <deque>
using namespace std;
typedef long long ll;
ll n, x, c, ans;
vector<ll> a;
ll gcd(ll a, ll b) {
while (b != 0) {
a %= b;
swap(a, b);
}
return a;
}
int main() {
cin >> n;
ans = -1;
for (ll i = 0; i < n; i++) {
cin >> x;
a.push_back(x);
}
for (ll i = 0; i < n; i++) {
c = a[i];
for (ll j = i + 1; j < n;j++) {
c = gcd(c, a[j]);
if (c == 1) {
ans = max(ans, j - i);
break;
}
}
if (c!=1) ans = max(ans, n-i);
}
cout << ans;
}
