Liczby naturalne dodatnie, które nie mają żadnego wspólnego dzielnika oprócz jedynki nazywamy liczbami względnie pierwszymi, np. 9 i 20.
Funkcja φ (czyt. "fi") Eulera lub tocjent, to funkcja nosząca nazwisko Eulera przypisująca każdej liczbie naturalnej dodatniej n liczbę liczb względnie z nią pierwszych i mniejszych od n. Funkcja Eulera odgrywa dużą rolę w teorii liczb. Ma też istotne zastosowania w kryptografii w badaniach nad złożonością szyfrów.
Oto kilka własności tej funkcji:
1. Jeśli p jest liczba pierwszą, to: φ(p)=p-1 2. Jeśli m i n są względnie pierwsze, to: φ(m*n)=φ(m)*φ(n) 3. Jeśli p jest liczbą pierwszą i n=pk, to: φ(n)=pk-1*(p-1)
Algorytm obliczający wartość tej funkcji mógłby wyglądać następująco:
φ(p) - zwróć ilość liczb mniejszych i względnie pierwszych z p 1. Jeśli p jest liczba pierwszą, to zwróć p-1 i zakończ 2. Znajdź m - najmniejszy dzielnik liczby p 3. Sprawdź ile razy m dzieli p - niech będzie to liczba k, czyli mk dzieli p, zaś mk+1 już nie dzieli p 3. Oznacza to, że p=mk*n 4. Jeśli n=1, to zwróć mk-1*(m-1) i zakończ 5. Zwróć φ(mk)*φ(n)
Na przykład \varphi(12)=\varphi(2^2\cdot 3)=\varphi(2^2)\cdot \varphi(3)=2^1\cdot(2-1)\cdot(3-1)=4, czyli istnieją 4 liczby względnie pierwsze z liczbą 12 i są to 1, 5, 7, 11.
Napisz program, który dla danych liczb naturalnych wyznaczy wartość funkcji φ Eulera.
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n
z zakresu
W każdym z kolejnych n wierszy zapisano po jednej liczbie całkowitej
z zakresu 2..109.
Wyjście zgodne z przykładem.
Dla danych podanych na wejściu:
3 3 12 2
Poprawną odpowiedzią jest wyjście:
2 4 1
Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5
Opcje zadania:
Biblioteki : iostream iomanip cmath Limit czasu : 0.1 s Limit pamięci : 32 MB Słowa niedozwolone :