Найти 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

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

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

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

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

	Найти max количество подряд идущих элементов последовательности, которые делятся на одно и то же натуральное число 19.07.2021, 13:31. Показов 5693. Ответов 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

ФедосеевПавел Модератор 8662 / 4498 / 1670 Регистрация: 01.02.2015 Сообщений: 13,915 Записей в блоге: 12
	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