Processing math: 100%

Ojlerova funkcija

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 1mn i nzd(m,n)=1.

Ulaz

Sa standardnog ulaza unosi se broj n (1n2109).

Izlaz

Na standardni izlaz ispisati samo traženi broj.

Primer

Ulaz

9

Izlaz

6

Objašnjenje

Brojevi uzajamno prosti sa brojem n su brojevi 1, 2, 4, 5, 7 i 8 i ima ih ukupno 6.

Primer 2

Ulaz

1

Izlaz

1

Objašnjenje

Broj 1 zadovoljava uslove 11 i nzd(1,1)=1.

Опис улаза

Опис излаза

Решење

Gruba sila

Funkciju φ(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č:

Dakle, ako se broj n rastavlja kao pk11pkmm, tada je

φ(n)=φ(pk11)φ(pkmm)=(pk11(p11p1))(pkmm(pm1pm))

odakle se pregrupisavanjem dobija

φ(n)=(pk11pkmm)(p11)(pm1)p1pm=n(p11)(pm1)p1pm

Ovo nam daje način za efikasno izračunavanje vrednosti φ(n). Primenjujemo algoritam rastavljanja broja na proste činioce. Svaki put kada naiđemo na prost činilac pi proizvod (koji inicijalizujemo na 1) množimo vrednošću pi1pi. Nakon toga iz broja uklanjamo sva pojavljivanja činioca pi (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(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;
}