Не могу решить задачу

Question

Не могу решить задачу второй день. Наверное я неправильно понял условие.

Забавная игра

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

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

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

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

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

Примеры

Ввод

3
6 10 15

Вывод

Пытался так, но получаю WL

#include <iostream>
#include <algorithm>

using namespace std;


int main() {
    int n,ans=0;
    cin>>n;
    int a[n+1];
    for(int i = 0;i<n;i++)cin>>a[i];
    a[n]=1;
    for(int i = 1;i<n;i++){
        int g=__gcd(a[i],a[i-1]); 
        if(g>1)ans++;
        while(g>1 && i<n){
            ans++;
            i++;
            g=__gcd(g,a[i]); 
        }
    }
    if(ans)cout<<ans; 
    else cout<<1;
    return 0;
}

Answer 1

Т.к ai небольшое(меньше 1000), то можно перебирать этот самый делитель в цикле от 2 до sqrt(1000), а вторым циклом проходить по массиву и искать наибольшую последовательность.

Answer 2

Если некоторый комплект чисел имеет общий делитель больший единицы, то эти же числа имеют общий простой делитель.

Заведём словарь: ключи простые числа, значения индексы. Перебираем числа a_k с доски. На итерации k словарь содержит пару p_i, j_i если все числа в интервале [j_i, k] делятся на p_i. На итерации k из словаря удаляются все записи которые не делят a_k. Все новые простые делители a_k добавляются в словарь со значениями k. Когда запись из словаря удаляется, обновляется максимум длины последовательности.

Сколько может быть различных элементов в словаре одновременно? Ключи словаря простые числа, на которые делится число a_k - другие мы вычеркнули. a_k <= 1000. 2 * 3 * 5 * 7 * 11 = 2310 > 1000. В словаре не более четырёх элементов.

Как быстро разложить a_k на простые? Проверить делимость на все простые меньшие 32 (sqrt(1000)). Их 11 штук.

import math


def prime_divisors(n):
    assert n <= 1000

    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31):
        if p * p > n:
            break
        if n % p == 0:
            yield p
            while n % p == 0:
                n //= p
    if n > 1:
        yield n


def lengths():
    n = int(input())
    divs = {}
    for i, a in enumerate(map(int, input().split())):
        new_divs = set(prime_divisors(a))
        old_divs = set(divs)
        for d in old_divs - new_divs:
            yield i - divs[d]
            del divs[d]
        for d in new_divs - old_divs:
            divs[d] = i
    for i in divs.values():
        yield n - i

        
print(max(lengths(), default=0))

$ time echo -e "3\n6 10 15" | python divisible-in-a-row.py 
2

real  0m0.027s
user  0m0.024s
sys   0m0.004s

Сто тысяч случайных чисел за четверть секунды:

$ wc -w temp.txt
100001 temp.txt

$ time python divisible-in-a-row.py < temp.txt
16

real  0m0.230s
user  0m0.228s
sys   0m0.000s

БЛОГ НА HUSL

Не могу решить задачу

Ответы (2 шт):