# Informatyka — zadanie 4.3

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2019-05/zad/4.3
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2019 (rozszerzona)
- rok: 2019
- poziom: rozszerzona
- typ: open
- punkty: 5
- działy: Programowanie i algorytmika

## Treść

Zadanie 4.3. (0-5)
W pliku liczby.txt znajdź najdłuższy ciąg liczb występujących kolejno po sobie i taki, że
największy wspólny dzielnik ich wszystkich jest większy od 1 (innymi słowy: istnieje taka
liczba całkowita większa od 1, która jest dzielnikiem każdej z tych liczb).
Jako odpowiedź podaj wartość pierwszej liczby w takim ciągu, długość ciągu oraz największą
liczbę całkowitą, która jest dzielnikiem każdej liczby w tym ciągu. W pliku z danymi jest tylko
jeden taki ciąg o największej długości.
Uwaga: Możesz skorzystać z zależności NWD(a, b, c) = NWD(NWD(a, b), c).
MIN_1R
Przykład:
Dla liczb 3, 7, 4, 6, 10, 2, 5 odpowiedzią jest 4 (pierwsza liczba ciągu), 4 (długość ciągu) i 2
(największy wspólny dzielnik), natomiast dla liczb 5, 70, 28, 42, 98, 1 odpowiedzią jest 70
(pierwsza liczba ciągu), 4 (długość ciągu) i 14 (największy wspólny dzielnik).
Odpowiedź dla pliku przyklad.txt: pierwsza liczba ciągu 90, długość 5, największy
wspólny dzielnik 10.
Do oceny oddajesz:
• plik tekstowy wyniki4.txt zawierający odpowiedzi do poszczególnych zadań
(odpowiedź do każdego zadania powinna być poprzedzona jego numerem)
• plik(i) zawierający(e) komputerową realizację Twoich obliczeń o nazwie(nazwach):
Wypełnia
egzaminator
Nr zadania
4.1.
4.2.
4.3.
Maks. liczba pkt.
3
4
5
Uzyskana liczba pkt.
MIN_1R

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

**Najdłuższy ciąg z NWD > 1 w pliku liczby.txt:**
- **Pierwsza liczba ciągu: 31968**
- **Długość ciągu: 150**
- **Największy wspólny dzielnik: 74**

## Sposób 1 - implementacja Python

**Idea:** przeglądamy ciąg od lewej. Utrzymujemy bieżący NWD i długość. Gdy NWD spadnie do 1 - kończymy ciąg, sprawdzamy czy jest najdłuższy, i zaczynamy nowy ciąg od bieżącej liczby. Wykorzystujemy własność: **NWD(a, b, c) = NWD(NWD(a, b), c)**.

```python
from math import gcd

with open('liczby.txt', encoding='utf-8') as f:
liczby = [int(linia) for linia in f]

najdluzszy_start_idx = 0
najdluzsza_dlugosc = 1
najdluzszy_nwd = liczby[0]

biezacy_start = 0
biezacy_nwd = liczby[0]

for i in range(1, len(liczby)):
nowy_nwd = gcd(biezacy_nwd, liczby[i])
if nowy_nwd > 1:
biezacy_nwd = nowy_nwd
dlugosc = i - biezacy_start + 1
if dlugosc > najdluzsza_dlugosc:
najdluzsza_dlugosc = dlugosc
najdluzszy_start_idx = biezacy_start
najdluzszy_nwd = biezacy_nwd
else:
# nowy ciąg startuje od liczby[i]
biezacy_start = i
biezacy_nwd = liczby[i]

print(f'pierwsza liczba: {liczby[najdluzszy_start_idx]}')
print(f'długość: {najdluzsza_dlugosc}')
print(f'dzielnik: {najdluzszy_nwd}')
# pierwsza liczba: 31968
# długość: 150
# dzielnik: 74

**Algorytm NWD (Euklides):**
```python
def nwd(a, b):
while b > 0:
a, b = b, a % b
return a

## Sposób 2 - implementacja Pascal

```pascal
program NajdluzszyCiagNWD;
var
f: TextFile;
liczby: array[1 500] of LongInt;
i, n: Integer;
biezacyStart, biezacyNWD, najStart, najDl, najNWD, nowyNWD, dl: LongInt;

function NWD(a, b: LongInt): LongInt;
var t: LongInt;
begin
while b > 0 do begin t := b; b := a mod b; a := t; end;
NWD := a;
end;

begin
AssignFile(f, 'liczby.txt');
Reset(f);
n := 0;
while not Eof(f) do begin Inc(n); ReadLn(f, liczby[n]); end;
CloseFile(f);

biezacyStart := 1; biezacyNWD := liczby[1];
najStart := 1; najDl := 1; najNWD := liczby[1];

for i := 2 to n do
begin
nowyNWD := NWD(biezacyNWD, liczby[i]);
if nowyNWD > 1 then
begin
biezacyNWD := nowyNWD;
dl := i - biezacyStart + 1;
if dl > najDl then
begin
najDl := dl; najStart := biezacyStart; najNWD := biezacyNWD;
end;
end
else
begin
biezacyStart := i; biezacyNWD := liczby[i];
end;
end;

WriteLn('pierwsza: ', liczby[najStart]);
WriteLn('długość: ', najDl);
WriteLn('dzielnik: ', najNWD);
end.

## Sposób 3 - implementacja C++

```cpp
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

long long nwd(long long a, long long b) {
while (b > 0) { long long t = b; b = a % b; a = t; }
return a;
}

int main() {
ifstream plik("liczby.txt");
vector<long long> liczby;
long long x;
while (plik >> x) liczby.push_back(x);

long long biezacyNWD = liczby[0], najNWD = liczby[0];
int biezacyStart = 0, najStart = 0, najDl = 1;

for (int i = 1; i < (int)liczby.size(); i++) {
long long nowy = nwd(biezacyNWD, liczby[i]);
if (nowy > 1) {
biezacyNWD = nowy;
int dl = i - biezacyStart + 1;
if (dl > najDl) {
najDl = dl;
najStart = biezacyStart;
najNWD = biezacyNWD;
}
} else {
biezacyStart = i;
biezacyNWD = liczby[i];
}
}

cout << "pierwsza: " << liczby[najStart] << endl;
cout << "długość: " << najDl << endl;
cout << "dzielnik: " << najNWD << endl;
return 0;
}

## Weryfikacja na przykładzie

Dla `przyklad.txt`: pierwsza 90, długość 5, dzielnik 10. Oznacza, że istnieje ciąg 5 kolejnych liczb (zaczynający się od 90), których wszystkie wartości są wielokrotnościami 10.

Dla przykładu z treści: `3, 7, 4, 6, 10, 2, 5`:
- 3,7 - gcd=1 (koniec ciągu 3 samodzielnie). Start nowego od 7. Ale gcd(7,4)=1 → start od 4.
- 4,6 → gcd=2. 4,6,10 → gcd=2. 4,6,10,2 → gcd=2. 4,6,10,2,5 → gcd=1. → Ciąg: 4,6,10,2, długość 4, gcd=2 ✓.

## Reference informatyczny - NWD (GCD)

> Reference - Algorytm Euklidesa:
> ```
> NWD(a, b):
> dopóki b > 0
> a, b = b, a mod b
> zwróć a
> ```
> Złożoność: O(log min(a, b)).
>
> Reference - Własności NWD:
> - NWD(a, b) = NWD(b, a mod b).
> - NWD(a, 0) = a.
> - NWD(a, b, c) = NWD(NWD(a, b), c).
> - NWD(a, b) ≥ 1 zawsze.
> - NWD(a, b) > 1 ⟺ a i b mają wspólny dzielnik > 1.

## Schemat oceniania CKE

> Klucz CKE (zadanie 4.3, max 5 pkt):
> - **1 pkt** - pierwsza liczba w ciągu (31968)
> - **2 pkt** - długość ciągu (150); 1 pkt jeśli różni się o 1 (np. liczenie od 0)
> - **2 pkt** - wspólny dzielnik (74)
> - **4 pkt** - za wariant (56536, 149, 74) - wynik z błędem off-by-one
> - **0 pkt** - błędna albo brak

## Typowe pułapki

- **Resetowanie NWD po nowym elemencie ZAMIAST liczenia od zera** - gdy NWD spadnie do 1, musisz zacząć NOWY ciąg od bieżącej liczby (NIE od następnej).
- **Aktualizacja długości tylko gdy NWD > 1** - wybór maksymalnej długości musi działać dla najdłuższego ciągu z NWD > 1, NIE każdego okna.
- **Off-by-one przy długości** - długość = i - start + 1 (gdy indeksowanie od 0).
- **Pierwsza liczba = `liczby[start]`** - pamiętaj, że pytanie pyta o WARTOŚĆ pierwszej liczby, nie jej indeks.
- **Złe NWD dla pierwszego ciągu jednoelementowego** - start jako liczba pojedyncza ma NWD = sama ta liczba.

## Złożoność obliczeniowa

- Czytanie pliku: O(n), n = 500.
- Główna pętla: O(n) iteracji, w każdej NWD: O(log(max)) ≈ 17 operacji dla wartości do 100 000.
- **Łącznie: O(n · log(max))** ≈ 8500 operacji.
- Pamięć: O(n) na tablicę liczb (lub O(1) gdy czytamy streaming).

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2019-05/zad/4.3)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2019-05%2Fzad%2F4.3)

## Podobne zadania

- [Zadanie 2](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/2) — Zadanie 2. Zapis symboliczny W pliku symbole.txt zapisano 2000 napisów. Każdy z nich jest zapisany w osobnym wierszu i składa się z dokładnie 12 znaków spośród:
- [Zadanie 7](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/7) — Zadanie 7. Poszukiwanie wody na Marsie W trzech plikach tekstowych o nazwach laziki.txt, obszary.txt, pomiary.txt zapisano informacje zawierające dane o poszuki
- [Zadanie 3](https://matura.lol/question/informatyka-2023-maj-matura-rozszerzona/zad/3) — Zadanie 3. Liczba Pi Pewien matematyk jest zafascynowany liczbą π ≈ 3,14159265 do tego stopnia, że zapisał jej rozwinięcie dziesiętne z dokładnością do 10 000 c
- [Zadanie 3](https://matura.lol/question/informatyka-2025-maj-matura-rozszerzona/zad/3) — Zadanie 3. Dron Tor lotu pewnego drona składa się z prostych odcinków. Lot rozpoczyna się w punkcie (0, 0), a kończy w punkcie (20000, 0). Dron poza startem i l

_Ostatnia aktualizacja danych: 2026-10-03_