@dmitrii2004

Найти количество чисел, делящихся на одно и тоже число?

Забавная игра
Вы с друзьями играете в следующую игру. Друзья пишут на доске подряд 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;
}
  • Вопрос задан
  • 83 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Есть 2 решения.

Во-первых, если бы вы умели бытсро проверять наибольший общий делитель чисел на отрезке, то можно было бы применить метод двух указателей. Найдите самый длинный отрезок, начинающийся в первом числе. Потом двигайте левую границу отрезка на 1 позицию и сдвигайте правую границу жадно пока можете. Вот вы нашли самый длинный отрезок из второй позиции. Опять двигайте левую границу на 1 и т.д. Выбирайте максимальный отрезок из всех найденных.

Быстро получать наибольший общий делитель можно за логарифм с помощью структуры данных дерево отрезков. Общая сложность будет O(n log n).

Второе решение такое: Раз числа на отрезке все делятся на что-то больше 1, то все они делятся на какое-то простое число. Значит задача состоит в том, чтобы найти самый длинный отрезок из чисел, делящихся на одно и тоже простое число. Значит вам надо разложить каждое число в массиве на простые множители и работать с ними отдельно. Далее, вам достаточно просто хранить для каждого простого множителя, какая длина у самого последнего отрезка из чисел с этим делителем и на какой позиции он закончился. Когда вы нашли, что текущее число делится на p, вам надо или начать новый отрезок или добавить текущую позицию к последнему отрезку.

Общая сложность у этого решения будет O(n sqrt(a)), но его можно ускорить, если предподсчитать для каждого числа от 1 до A один из его простых делителей.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
31 июл. 2021, в 12:44
15000 руб./за проект
31 июл. 2021, в 12:18
5000 руб./за проект
31 июл. 2021, в 12:17
200000 руб./за проект