Napiši program koji određuje koliko ima prirodnih brojeva \(m\) manjih ili jednakih od datog broja \(n\) koji su uzajamno prosti sa \(n\) tj. za koje je \(1 \leq m \leq n\) i \(nzd(m, n) = 1\).
Sa standardnog ulaza unosi se broj \(n\) (\(1 \leq n \leq 2\cdot 10^9\)).
Na standardni izlaz ispisati samo traženi broj.
9
6
Brojevi uzajamno prosti sa brojem \(n\) su brojevi 1, 2, 4, 5, 7 i 8 i ima ih ukupno 6.
1
1
Broj 1 zadovoljava uslove \(1 \leq 1\) i \(nzd(1, 1) = 1\).
Funkciju \(\varphi(n)\) koja izračunava broj brojeva uzajamno prostih sa \(n\) proučavao je Leonard Ojler, pa se ova funkcija obično naziva Ojlerova funkcija.
Naivni pristup izračunavanju zasnivao bi se na brojanju elemenata koji su uzajamno prosti sa datim brojem \(n\) (dakle, na brojanju elemenata koji zadovoljavaju dati uslov), pri čemu bismo proveru da li su dva broja uzajamno prosta mogli zasnovati na izračunavanju NZD i primeni Euklidovog algoritma (brojevi su uzajamno prosti ako i samo ako im je NZD jednak 1). Euklidov algoritam je opisan u zadatku [euklid].
#include <iostream>
using namespace std;
// izracunavanje najveceg zajednickog delioca brojeva a i b
int nzd(int a, int b) {
// Euklidov algoritam
while (b > 0) { // dok b ne postane nula
int tmp = b; // par (a, b) menjamo parom (b, a % b)
b = a % b; // jer je nzd(a, b) = nzd(b, a % b)
a = tmp;
}
return a; // nzd(a, 0) = a
}
// broj brojeva iz intervala [1, n] koji su uzajamno prosti sa n
int phi(int n) {
int broj = 0;
for (int i = 1; i <= n; i++)
if (nzd(i, n) == 1)
broj++;
return broj;
}
int main() {
// izracunavamo vrednost phi za uneti broj
int n;
cin >> n;
cout << phi(n) << endl;
return 0;
}Ipak, matematička svojstva Ojlerove funkcije nam daju način da njenu vrednost mnogo brže izračunamo. Evo o kojim svojstvima je reč:
Funkcija \(\varphi\) je multiplikativna, tj. ako su \(a\) i \(b\) uzajmno prosti brojevi, tada je \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\). Najlakše je razumeti zašto je to tako kada se brojevi od \(1\) do \(a \cdot b\) napišu u \(a\) redova po \(b\) brojeva. Tada će oni brojevi koji su uzajamno prosti sa \(a \cdot b\) da se nađu u \(\varphi(a)\) redova po \(\varphi(b)\) brojeva. Ova osobina je značajna jer vrednosti multiplikativnih funkcija mogu veoma efikasno da se izračunaju na osnovu razlaganja argumenta na proste činioce i izračunavanja vrednosti funkcije za proste činioce. Ta tehnika je opisana, na primer, u zadatku [broj_i_zbir_delilaca].
Ako je \(p\) prost broj, tada je \(\varphi(p) = p-1\), jer su svi brojevi koji su manji od \(p\), uzajamno prosti sa \(p\).
Ako je \(p\) prost broj, broj brojeva uzajamno prostih sa brojem \(p^k\) je \(\varphi(p^k) = p^k - p^{k-1} = p^k\cdot \left(\frac{p - 1}{p}\right)\). Zaista, od svih \(p^k\) brojeva iz intervala \([1, p^k]\), jedini koji nisu uzajamno prosti sa \(p^k\) su umnošci broja \(p\), a to su brojevi \(p\), \(2p\), \(3p\), …, \(p^{k-1}\cdot p\). Njih ima \(p^{k-1}\), što dokazuje tvrđenje.
Dakle, ako se broj \(n\) rastavlja kao \(p_1^{k_1}\cdot \ldots \cdot p_m^{k_m}\), tada je
\[\varphi(n) = \varphi(p_1^{k_1}) \cdot \ldots \cdot \varphi(p_m^{k_m}) = \left(p_1^{k_1}\cdot \left(\frac{p_1-1}{p_1}\right)\right)\cdot \ldots \cdot \left(p_m^{k_m} \cdot \left (\frac{p_m-1}{p_m}\right)\right)\]
odakle se pregrupisavanjem dobija
\[\varphi(n) = (p_1^{k_1} \ldots p_m^{k_m}) \frac{(p_1-1)\cdot \ldots \cdot (p_m-1)}{p_1\cdot \ldots \cdot p_m} = n\cdot \frac{(p_1-1)\cdot \ldots \cdot (p_m-1)}{p_1\cdot \ldots \cdot p_m}\]
Ovo nam daje način za efikasno izračunavanje vrednosti \(\varphi(n)\). Primenjujemo algoritam rastavljanja broja na proste činioce. Ovaj algoritam je opisan u zadatku [rastavljanje_na_proste_cinioce]. Svaki put kada naiđemo na prost činilac \(p_i\) proizvod (koji inicijalizujemo na 1) množimo vrednošću \(\frac{p_i - 1}{p_i}\). Nakon toga iz broja uklanjamo sva pojavljivanja činioca \(p_i\) (za svako pojavljivanje činioca, bez obzira na njegovu višestrukost, proizvod se množi samo jednim činiocem).
Na kraju kao rezultat vraćamo akumulirani proizvod pomnožen vrednošću broja \(n\). Pošto se \(n\) menja tokom određivanja njegovih prostih činilaca, bolje rešenje je proizvod na početku inicijalizovati na \(n\).
Složenost odgovara rastavljanju na proste činioce i za broj \(n\) iznosi \(O(\sqrt{n})\).
#include <iostream>
using namespace std;
// broj brojeva manjih od n koji su uzajamno prosti sa n
int phi(int n) {
// Ojlerova formula kaze da je taj broj jednak
// n * proizvod(1 - 1/p) za sve proste brojeve p koji dele broj n
int d = 2;
int proizvod = n;
// dok broj n ne postane prost
while (d*d <= n) {
if (n % d == 0) {
// nasli smo nov prost faktor pa azuriramo proizvod
proizvod = (proizvod / d) * (d - 1);
// uklanjamo ostala pojavljivanja tog faktora
while (n % d == 0)
n /= d;
}
// prelazimo na sledeceg kandidata
d++;
}
// n je prost broj, pa treba azurirati proizvod i za njega
if (n > 1)
proizvod = (proizvod / n) * (n - 1);
// vracamo rezultat
return proizvod;
}
int main() {
int n;
cin >> n;
cout << phi(n) << endl;
return 0;
}Funkciju \(\varphi(n)\) koja izračunava broj brojeva uzajamno prostih sa \(n\) proučavao je Leonard Ojler, pa se ova funkcija obično naziva Ojlerova funkcija.
Naivni pristup izračunavanju zasnivao bi se na brojanju elemenata koji su uzajamno prosti sa datim brojem \(n\) (dakle, na brojanju elemenata koji zadovoljavaju dati uslov), pri čemu bismo proveru da li su dva broja uzajamno prosta mogli zasnovati na izračunavanju NZD i primeni Euklidovog algoritma (brojevi su uzajamno prosti ako i samo ako im je NZD jednak 1). Euklidov algoritam je opisan u zadatku [euklid].
using System;
class Program
{
// izracunavanje najveceg zajednickog delioca brojeva a i b
static int nzd(int a, int b)
{
// Euklidov algoritam
while (b > 0)
{ // dok b ne postane nula
int tmp = b; // par (a, b) menjamo parom (b, a % b)
b = a % b; // jer je nzd(a, b) = nzd(b, a % b)
a = tmp;
}
return a; // nzd(a, 0) = a
}
// broj brojeva iz intervala [1, n] koji su uzajamno prosti sa n
static int phi(int n)
{
int broj = 0;
for (int i = 1; i <= n; i++)
if (nzd(i, n) == 1)
broj++;
return broj;
}
static void Main()
{
// izracunavamo vrednost phi za uneti broj
int n = int.Parse(Console.ReadLine());
Console.WriteLine(phi(n));
}
}Ipak, matematička svojstva Ojlerove funkcije nam daju način da njenu vrednost mnogo brže izračunamo. Evo o kojim svojstvima je reč:
Funkcija \(\varphi\) je multiplikativna, tj. ako su \(a\) i \(b\) uzajmno prosti brojevi, tada je \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\). Najlakše je razumeti zašto je to tako kada se brojevi od \(1\) do \(a \cdot b\) napišu u \(a\) redova po \(b\) brojeva. Tada će oni brojevi koji su uzajamno prosti sa \(a \cdot b\) da se nađu u \(\varphi(a)\) redova po \(\varphi(b)\) brojeva. Ova osobina je značajna jer vrednosti multiplikativnih funkcija mogu veoma efikasno da se izračunaju na osnovu razlaganja argumenta na proste činioce i izračunavanja vrednosti funkcije za proste činioce. Ta tehnika je opisana, na primer, u zadatku [broj_i_zbir_delilaca].
Ako je \(p\) prost broj, tada je \(\varphi(p) = p-1\), jer su svi brojevi koji su manji od \(p\), uzajamno prosti sa \(p\).
Ako je \(p\) prost broj, broj brojeva uzajamno prostih sa brojem \(p^k\) je \(\varphi(p^k) = p^k - p^{k-1} = p^k\cdot \left(\frac{p - 1}{p}\right)\). Zaista, od svih \(p^k\) brojeva iz intervala \([1, p^k]\), jedini koji nisu uzajamno prosti sa \(p^k\) su umnošci broja \(p\), a to su brojevi \(p\), \(2p\), \(3p\), …, \(p^{k-1}\cdot p\). Njih ima \(p^{k-1}\), što dokazuje tvrđenje.
Dakle, ako se broj \(n\) rastavlja kao \(p_1^{k_1}\cdot \ldots \cdot p_m^{k_m}\), tada je
\[\varphi(n) = \varphi(p_1^{k_1}) \cdot \ldots \cdot \varphi(p_m^{k_m}) = \left(p_1^{k_1}\cdot \left(\frac{p_1-1}{p_1}\right)\right)\cdot \ldots \cdot \left(p_m^{k_m} \cdot \left (\frac{p_m-1}{p_m}\right)\right)\]
odakle se pregrupisavanjem dobija
\[\varphi(n) = (p_1^{k_1} \ldots p_m^{k_m}) \frac{(p_1-1)\cdot \ldots \cdot (p_m-1)}{p_1\cdot \ldots \cdot p_m} = n\cdot \frac{(p_1-1)\cdot \ldots \cdot (p_m-1)}{p_1\cdot \ldots \cdot p_m}\]
Ovo nam daje način za efikasno izračunavanje vrednosti \(\varphi(n)\). Primenjujemo algoritam rastavljanja broja na proste činioce. Ovaj algoritam je opisan u zadatku [rastavljanje_na_proste_cinioce]. Svaki put kada naiđemo na prost činilac \(p_i\) proizvod (koji inicijalizujemo na 1) množimo vrednošću \(\frac{p_i - 1}{p_i}\). Nakon toga iz broja uklanjamo sva pojavljivanja činioca \(p_i\) (za svako pojavljivanje činioca, bez obzira na njegovu višestrukost, proizvod se množi samo jednim činiocem).
Na kraju kao rezultat vraćamo akumulirani proizvod pomnožen vrednošću broja \(n\). Pošto se \(n\) menja tokom određivanja njegovih prostih činilaca, bolje rešenje je proizvod na početku inicijalizovati na \(n\).
Složenost odgovara rastavljanju na proste činioce i za broj \(n\) iznosi \(O(\sqrt{n})\).
using System;
class Program
{
static int phi(int n)
{
// Ojlerova formula kaze da je taj broj jednak
// n * proizvod(1 - 1/p) za sve proste brojeve p koji dele broj n
int d = 2;
int proizvod = n;
// dok broj n ne postane prost
while (d*d <= n) {
if (n % d == 0) {
// nasli smo nov prost faktor pa azuriramo proizvod
proizvod = (proizvod / d) * (d - 1);
// uklanjamo ostala pojavljivanja tog faktora
while (n % d == 0)
n /= d;
}
// prelazimo na sledeceg kandidata
d++;
}
// n je prost broj, pa treba azurirati proizvod i za njega
if (n > 1)
proizvod = (proizvod / n) * (n - 1);
// vracamo rezultat
return proizvod;
}
static void Main()
{
int n = int.Parse(Console.ReadLine());
Console.WriteLine(phi(n));
}
}