Найти max количество подряд идущих элементов последовательности, которые делятся на одно и то же натуральное число

@dmitrii2000 · Регистрация: 03.05.2020

Студворк — интернет-сервис помощи студентам

Забавная игра
Вы с друзьями играете в следующую игру. Друзья пишут на доске подряд N натуральных чисел. Ваша задача — найти как можно больше подряд идущих чисел, которые бы делились на одно и то же число, большее 1. Так как вручную искать ответ сложно, вы решили написать программу, которая сделает работу за вас.

Входные данные

В первой строке входных данных задано число N(1 ≤ N ≤ 100000). Во второй строке записано через пробел N целых чисел A1...AN(1 ≤ Ai ≤ 1000, 1 ≤ i ≤ N). Это те самые числа, которые написали ваши друзья. Они даны в том же порядке, в котором они расположены на доске.

Выходные данные

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

Примеры
Ввод
3
6 10 15
Dsdjl
2

Байт · 19.07.2021, 14:02

dmitrii2000, находить НОД умеете? Двух чисел? Нескольких?

Добавлено через 1 минуту
Старайтесь соблюдать правило 4.7

@LegionK · 19.07.2021, 18:49

Сообщение от Байт

находить НОД умеете? Двух чисел? Нескольких?

Боюсь не поможет.

dmitrii2000, вроде можно за n*log*log решить, если написать бинарный поиск по ответу + дерево отрезков на нод.

А можно перебрать все простые числа до 1000, их около 100, и для каждого числа найти максимальный отрезок, в котором каждый элемент делится на это число. Потом выбрать наибольший и вывести. Это уровень ЕГЭ, вы справитесь. Нет, код я вам не отправлю, мне это неинтересно писать.

Байт · 19.07.2021, 22:37

Сообщение от LegionK

Боюсь не поможет.

почему же? Если бы ТС ответил на мой вопрос, мы бы с ним с грехом пополам набросали бы простенький код. И моя цель - заставить его немножко попытаться думать своей головой, а не ждать готового решения. Помочь, научить - рад. Делать за него - не интересно.
С вами полностью солидарен.

@dmitrii2000 · 20.07.2021, 13:38 **[ТС]**

Скиньте код пожалуйста

Байт · 20.07.2021, 13:59

Сообщение от dmitrii2000

Скиньте код пожалуйста

У меня его просто нет. Чтобы скинуть, надо его сначала создать. А зачем мне это?

@dmitrii2000 · 20.07.2021, 14:22 **[ТС]**

Помогите пожалуйста код не проходит по времени

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}

Байт · 20.07.2021, 16:55

Сообщение от dmitrii2000

typedef long long ll;

Это зачем? Числа в задаче совсем не большие. Достаточно int

Добавлено через 9 минут
Код, похоже, рабочий. Сам писал?
Но слишком лобовой. Тут потоньше надо...

Добавлено через 2 часа 16 минут
Один из путей оптимизации кодаЖ
Во внешнем цикле пропускать a[i], взаимно простые с те, которое нарушило делимость....
Все равно от них ничего хорошего ждать не приходится...

ФедосеевПавел · 05.08.2021, 08:25

Что то пришла в голову мысль:
1. в массиве искать НОД двух соседних чисел массива и тут же перезаписывать (заменять элемент на НОД) массив, который при этом уменьшится на 1 элемент.
2. операцию повторять пока все элементы массива не станут равны 1 или до сокращения длины массива до 1.
3. количество итераций и будет ответом.
4. для оптимизации пропускать элементы с 1, сокращать массив слева и справа при равенстве элементов 1.

Байт · 05.08.2021, 12:23

[quote="ФедосеевПавел;15650702"]Что то пришла в голову мысль[/quoto(e]Мысль интересная, но это, имхо, O(n²) как минимум

ФедосеевПавел · 05.08.2021, 13:27

Да, похоже, у меня не лучший вариант. А других собственных пока и нет.

Согласен с LegionK - можно воспользоваться ограниченным диапазоном элементов массива

Сообщение от LegionK

перебрать все простые числа до 1000, их около 100, и для каждого числа найти максимальный отрезок, в котором каждый элемент делится на это число. Потом выбрать наибольший и вывести

А вот вторую идею не понял

Сообщение от LegionK

бинарный поиск по ответу + дерево отрезков на нод

Байт · 05.08.2021, 14:55

Сообщение от ФедосеевПавел

А других собственных пока и нет.

Согласен. Мой - тоже не шибко хорош

@LegionK · 16.08.2021, 18:20

Сообщение от ФедосеевПавел

А вот вторую идею не понял

Если все числа из подотрезка l...r делятся на какое-то число большее 1, то это значит, что нод всех элементов из этого отрезка будет больше единицы. Такой отрезок пусть назовем хорошим.

Т.к если в массиве присутствует хороший отрезок длины k, то будут присутствовать и все отрезки длины 1,2,...k-1, (хотя бы как подотрезки этого подотрезка). Соответственно если обозначить функцию f(t) как "присутствует ли хороший отрезок длины t в массиве", то для значений t от 1 до n значения f(t) будут : 1, 1, 1, 1, 1....,1, 0, 0, 0, 0, 0...... Вот ту последнюю единицу нам и надо найти. Сделать это можно при помощи бинарного поиска. Всё что осталось - написать функцию f. То есть уметь проверять, есть ли у нас в массиве хороший подотрезок нужной длины.

Пусть нам дано число k и нужно проверить, есть ли хороший отрезок длины k. Можно идти по массиву слева направо и для каждого i проверять, подходит ли нам отрезок i...i+k при помощи дерева отрезков на нод.

Ну в целом всё. Для данной задачи это излишне и асимптотика будет n*log*log*log. Это >= n*1000, но это все равно на порядок-два меньше, чем n*n.

Решается эта задача как я написал выше про простые числа. Не хотел вам отвечать потому что идея эта здесь ненужная и заметил я это просто так, но недавно увидел задачу сводящуюся к этой, а именно к вот этому методу (а не первому, потому что нету ограничения такого маленького на сами числа массива) и подумал, что вам, может быть, будет все же интересно. Вот задача https://codeforces.com/contest/1549/problem/D
чтобы решение посмотреть в правом нижнем углу "разбор задач". Там предлагается вместо дерева отрезков использовать разреженную таблицу, чтобы от одного логарифма в произведении избавиться, но я эту структуру не знаю.

Байт · 16.08.2021, 21:56

LegionK, Если я вас правильно понял, основная идея, заключается в том, что вы ищите Хороший отрезок дли N, при неудаче, длины N/2, дальше N/4 или 3N/4. И так далее...
Или я не врубаюсь?

@LegionK · 17.08.2021, 02:10

Байт, Да, как обычный бинарный поиск.

@TheCalligrapher · 17.08.2021, 05:31

Сообщение от dmitrii2000

Во второй строке записано через пробел N целых чисел A1...AN(1 ≤ Ai ≤ 1000, 1 ≤ i ≤ N)

Сразу ясно, что в качестве делителей нужно рассматривать только простые числа. В указанном димпазоне простых чисел немного. В чем проблема найти самый длинный отрезок делимости за один проход лобовым алгоримом? К чему тут какой-то бинарный поиск? Чего в чем?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
 
int main() 
{
  struct { const unsigned p; unsigned n; } primes[] = 
  {
    {   2 }, {   3 }, {   5 }, {   7 }, {  11 }, {  13 }, {  17 }, {  19 }, 
    {  23 }, {  29 }, {  31 }, {  37 }, {  41 }, {  43 }, {  47 }, {  53 }, 
    {  59 }, {  61 }, {  67 }, {  71 }, {  73 }, {  79 }, {  83 }, {  89 }, 
    {  97 }, { 101 }, { 103 }, { 107 }, { 109 }, { 113 }, { 127 }, { 131 }, 
    { 137 }, { 139 }, { 149 }, { 151 }, { 157 }, { 163 }, { 167 }, { 173 }, 
    { 179 }, { 181 }, { 191 }, { 193 }, { 197 }, { 199 }, { 211 }, { 223 }, 
    { 227 }, { 229 }, { 233 }, { 239 }, { 241 }, { 251 }, { 257 }, { 263 }, 
    { 269 }, { 271 }, { 277 }, { 281 }, { 283 }, { 293 }, { 307 }, { 311 }, 
    { 313 }, { 317 }, { 331 }, { 337 }, { 347 }, { 349 }, { 353 }, { 359 }, 
    { 367 }, { 373 }, { 379 }, { 383 }, { 389 }, { 397 }, { 401 }, { 409 }, 
    { 419 }, { 421 }, { 431 }, { 433 }, { 439 }, { 443 }, { 449 }, { 457 }, 
    { 461 }, { 463 }, { 467 }, { 479 }, { 487 }, { 491 }, { 499 }, { 503 }, 
    { 509 }, { 521 }, { 523 }, { 541 }, { 547 }, { 557 }, { 563 }, { 569 }, 
    { 571 }, { 577 }, { 587 }, { 593 }, { 599 }, { 601 }, { 607 }, { 613 }, 
    { 617 }, { 619 }, { 631 }, { 641 }, { 643 }, { 647 }, { 653 }, { 659 }, 
    { 661 }, { 673 }, { 677 }, { 683 }, { 691 }, { 701 }, { 709 }, { 719 }, 
    { 727 }, { 733 }, { 739 }, { 743 }, { 751 }, { 757 }, { 761 }, { 769 }, 
    { 773 }, { 787 }, { 797 }, { 809 }, { 811 }, { 821 }, { 823 }, { 827 }, 
    { 829 }, { 839 }, { 853 }, { 857 }, { 859 }, { 863 }, { 877 }, { 881 }, 
    { 883 }, { 887 }, { 907 }, { 911 }, { 919 }, { 929 }, { 937 }, { 941 }, 
    { 947 }, { 953 }, { 967 }, { 971 }, { 977 }, { 983 }, { 991 }, { 997 } 
  }; 
 
  unsigned n = 0;
  std::cin >> n;
 
  unsigned m = 0;
 
  for (; n > 0; --n)
  {
    unsigned i = 0;
    std::cin >> i;
 
    for (auto &p : primes)
    {
      if (p.p > i)
        break;
 
      if (i % p.p != 0)
        p.n = 0;
      else if (++p.n > m)
        m = p.n;
    }
  }
 
  std::cout << m << std::endl;
}

@LegionK · 17.08.2021, 09:29

Сообщение от TheCalligrapher

Сразу ясно, что в качестве делителей нужно рассматривать только простые числа. В указанном димпазоне простых чисел немного. В чем проблема найти самый длинный отрезок делимости за один проход лобовым алгоримом?

Сообщение от LegionK

А можно перебрать все простые числа до 1000, их около 100, и для каждого числа найти максимальный отрезок, в котором каждый элемент делится на это число. Потом выбрать наибольший и вывести

Сообщение от TheCalligrapher

К чему тут какой-то бинарный поиск?

Сообщение от LegionK

Не хотел вам отвечать потому что идея эта здесь ненужная и заметил я это просто так, но недавно увидел задачу сводящуюся к этой, а именно к вот этому методу (а не первому, потому что нету ограничения такого маленького на сами числа массива) и подумал, что вам, может быть, будет все же интересно

Сообщение от TheCalligrapher

Чего в чем?

Сообщение от LegionK

бинарный поиск по ответу

...

@TheCalligrapher · 17.08.2021, 17:56

Сообщение от LegionK

бинарный поиск по ответу

По-прежнему не увидел в этой последовательности фраз ответа на свои вопросы: К чему тут какой-то бинарный поиск? Чего в чем?

Бинарный поиск производится по упорядоченной последовательности. Где здесь упорядоченная проследовательность? Упорядоченная проследовательность чего и как она упорядочена?

@LegionK · 17.08.2021, 18:02

Сообщение от TheCalligrapher

По-прежнему не увидел в этой последовательности фраз ответа на свои вопросы

Я вам соболезную. Очень трагичная новость. Хотя никак не пойму почему мне должно быть не все равно, что кто-то не умеет читать, но я вам все равно соболезную на всякий случай.

@TheCalligrapher · 17.08.2021, 18:07

Не по теме:

Сообщение от LegionK

Я вам соболезную. Очень трагичная новость. Хотя никак не пойму почему мне должно быть не все равно, что кто-то не умеет читать, но я вам все равно соболезную на всякий случай.

^^^ А, ну то есть это просто тролль, народ, который просто заваливает форум шлаком. Это тоже результат.

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение Это мой обзор планшета X220 с точки зрения школьника. Недавно я решила попытаться уменьшить свой. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202

	Найти max количество подряд идущих элементов последовательности, которые делятся на одно и то же натуральное число 19.07.2021, 13:31. Показов 5633. Ответов 20 Метки нет (Все метки) Забавная игра Вы с друзьями играете в следующую игру. Друзья пишут на доске подряд N натуральных чисел. Ваша задача — найти как можно больше подряд идущих чисел, которые бы делились на одно и то же число, большее 1. Так как вручную искать ответ сложно, вы решили написать программу, которая сделает работу за вас. Входные данные В первой строке входных данных задано число N(1 ≤ N ≤ 100000). Во второй строке записано через пробел N целых чисел A1...AN(1 ≤ Ai ≤ 1000, 1 ≤ i ≤ N). Это те самые числа, которые написали ваши друзья. Они даны в том же порядке, в котором они расположены на доске. Выходные данные Ваша программа должна вывести одно целое число — наибольшее количество подряд идущих чисел заданной последовательности, которые бы делились на одно и то же натуральное число, большее 1. Примеры Ввод 3 6 10 15 Dsdjl 2 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	19.07.2021, 14:02
	dmitrii2000, находить НОД умеете? Двух чисел? Нескольких? Добавлено через 1 минуту Старайтесь соблюдать правило 4.7 0

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	20.07.2021, 13:38 [ТС]
	Скиньте код пожалуйста 0

ФедосеевПавел Модератор 8645 / 4480 / 1669 Регистрация: 01.02.2015 Сообщений: 13,888 Записей в блоге: 11
	05.08.2021, 08:25
	Что то пришла в голову мысль: 1. в массиве искать НОД двух соседних чисел массива и тут же перезаписывать (заменять элемент на НОД) массив, который при этом уменьшится на 1 элемент. 2. операцию повторять пока все элементы массива не станут равны 1 или до сокращения длины массива до 1. 3. количество итераций и будет ответом. 4. для оптимизации пропускать элементы с 1, сокращать массив слева и справа при равенстве элементов 1. 1

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	05.08.2021, 12:23
	[quote="ФедосеевПавел;15650702"]Что то пришла в голову мысль[/quoto(e]Мысль интересная, но это, имхо, O(n²) как минимум 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	16.08.2021, 21:56
	LegionK, Если я вас правильно понял, основная идея, заключается в том, что вы ищите Хороший отрезок дли N, при неудаче, длины N/2, дальше N/4 или 3N/4. И так далее... Или я не врубаюсь? 0

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	17.08.2021, 02:10
	Байт, Да, как обычный бинарный поиск. 0