Gruba sila

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).

#include <iostream>

using namespace std;

int nzd(int a, int b) 
{
    while (b > 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

int phi(int n) 
{
    int count = 0;

    for (int i = 1; i <= n; i++) {
        if (nzd(i, n) == 1) {
            count++;
        }
    }

    return count;
}

int main() 
{
    int n;
    cin >> n;

    cout << phi(n) << endl;

    return 0;
}

Rastavljanje na proste činioce

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.

• 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. 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\).

#include <iostream>

using namespace std;

int phi(int n) 
{
    int p = 2;
    int prod = n;
    while (p * p <= n) {
        if (n % p == 0) {
            prod = (prod / p) * (p - 1);
            while (n % p == 0) {
                n /= p;
            }
        }
        p++;
    }
    if (n > 1) {
        prod = (prod / n) * (n - 1);
    }
    return prod;
}

int main()
{
    int n;
    cin >> n;

    cout << phi(n) << endl;

    return 0;
}