Editing 3273 - cmmdcsecv

Sursa: [https://www.pbinfo.ro/probleme/3273/cmmdcsecv 3273 - cmmdcsecv]
----
Fie un șir a1, a2, …, an de numere naturale. O secvență a șirului este o succesiune de elemente alăturate din șir, deci de forma ai, ai+1, …, aj. Lungimea acestei secvențe este dată de numărul de elemente ale secvenței, adică j – i + 1.



== Cerinţa ==
Să se determine o secvență de lungime maximă din șir cu proprietatea că cel mai mare divizor comun al numerelor din secvență este strict mai mare decât 1.


== Date de intrare ==
Fișierul de intrare cmmdcsecv.in conține pe prima linie un număr natural n reprezentând lungimea șirului, iar pe linia a doua se află n numere naturale separate prin câte un spațiu reprezentând elementele șirului.


== Date de ieșire == 
Fișierul de ieșire cmmdcsecv.out va conține un singur număr natural reprezentând lungimea maximă a unei secvențe care are cel mai mare divizor comun strict mai mare decât 1.

== Restricţii şi precizări ==
* 3 ≤ n ≤ 100.000
* 1 ≤ ai ≤ 1000, pentru orice 1 ≤ i ≤ n
== Exemplu ==
; Intrare
: 6
: 15 28 14 56 42 5
; Ieșire
: 4

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3273 - cmmdcsecv

import math

def read_input():
    with open("cmmdcsecv.in", "r") as f:
        n = int(f.readline())
        arr = list(map(int, f.readline().split()))
    return n, arr

def cmmdcsecv(n, arr):
    max_len = 0  # lungimea maxima a secventei
    for i in range(n):
        d = arr[i]  # cel mai mare divizor comun
        for j in range(i + 1, n):
            d = math.gcd(d, arr[j])
            if d > 1:
                max_len = max(max_len, j - i + 1)
    return max_len

def validate_output(result):
    with open("cmmdcsecv.out", "r") as f:
        expected_result = int(f.readline())
    assert result == expected_result, f"Error: expected {expected_result}, but got {result}"

if __name__ == "__main__":
    n, arr = read_input()
    result = cmmdcsecv(n, arr)
    validate_output(result)
    print(result)


</syntaxhighlight>
== Explicatie Rezolvare ==
Pentru a rezolva această problemă, putem folosi o metodă similară cu algoritmul de căutare a celei mai lungi subsecvențe crescătoare (LIS). Vom parcurge șirul și vom calcula cel mai mare divizor comun (CMMD) între fiecare element și toate elementele următoare. Dacă cel mai mare divizor comun este strict mai mare decât 1, atunci avem o secvență validă și vom actualiza lungimea maximă a secvenței.