Kezdőlap


Feladat:	S.139	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2019/december, 555 - 556. oldal		PDF \| MathML
Témakör(ök):	Nehezebb feladat, Számítástudomány

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Adott $N$ darab pozitív egész szám. Adjuk meg, hogy hány olyan számpár van közöttük, amelyek tagjai relatív prímek.
Bemenet: az első sor tartalmazza az $N$ értékét. A második sor tartalmazza szóközökkel elválasztva az $N$ darab pozitív egészet.
Kimenet: egyetlen sor, mely a relatív prím számpárok számát tartalmazza.
Példa:

\begin{matrix} Bemenet & Kimenet \\ 5 & 8 \\ 31 88 41 72 9 \end{matrix}

Korlátok:

3 \leq N \leq 50 000

1 \leq számok \leq 500 000

. Időkorlát: 0,3 mp.
Értékelés: a pontok 30%-a kapható, ha

N \leq 1000

.
Beküldendő egy s139.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.