Editing 3227 - Tramvaie


= Enunt =
Timp de <code>t</code> zile ''Cebîșev'' a numărat in drum spre școală <code>x</code> mașini și <code>y</code> tramvaie. Se știe că numărul de tramvaie este egal cu numărul de numere mai mici sau egale cu <code>x</code> si prime cu acesta.

= Cerința =
Știindu-se numărul de zile si numărul de mașini numărate în fiecare zi, calculați pentru fiecare zi numărul de tramvaie numărate de ''Cebîșev''.

= Date de intrare =
Fișierul de intrare este <code>tramvaie.in</code>

Acesta conține pe primul rând un număr natural <code>t</code>, reprezentând numărul de zile.

Pe a doua linie a fișierului de intrare se găsesc <code>t</code> numere, reprezentând numarul de masini văzute în fiecare zi de ''Cebîșev''.

= Date de iesire =
Fișierul de ieșire este <code>tramvaie.out</code>

Acesta conține <code>t</code> numere reprezentând numărul de tramvaie văzute de ''Cebîșev'' în fiecare zi.

= Restricții și precizări =

* <code>0 < x, y, t < 1 000 006</code>
* Se consideră că orice număr este prim cu <code>1</code>.

= Exemplul 1: =
<code>tramvaie.in</code>
 2
 2 3
<code>tramvaie.out</code>
 1 2

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys

prob = "tramvaie"
in_file = open(prob + ".in", "r")
out_file = open(prob + ".out", "w")
sys.stdin = in_file
sys.stdout = out_file

N = int(input())
euler = [i for i in range(1000006)]
for i in range(2, 1000006):
    if euler[i] == i:
        euler[i] -= 1
        for j in range(2, 1000006, i):
            euler[j * i] = euler[j * i] // i * (i - 1)

for n in range(1, N + 1):
    temp = int(input())
    print(euler[temp], end=" ")

in_file.close()
out_file.close()


</syntaxhighlight>