Ułamki ( omówienie )

11.08.2010

Jeżeli ułamek a/b spełnia warunki zadania to znaczy, że po jego skróceniu zarówno licznik i mianownik są mniejsze równe M. 

W rozwiązaniu wzorcowym rozpatrujemy wszystkie nieskracalne ułamki x/y (1 <= x, y <= M) i patrzymy ile jest ułamków z/w (z,w <= N) takich że z/w = x/y. Robienie tego wprost wymaga rozpatrzenia M^2 ułamków co oczywiście nie zmieści się w czasie. Należy rozpatrywać ułamki grupami.

Najpierw rozpatrzmy przypadek gdy licznik = mianownik. Jest N ułamków spełniających wymogi, które skracają się do 1/1. Przypadki licznik < mianownik oraz licznik > mianownik są symetryczne. Omówiony zostanie przypadek licznik < mianownik.

Rozpatrzmy grupe nieskracalnych ułamków mniejszych od 1, których mianownik jest równy X. Ilość nieskracalnych ułamków o mianowniku równym X to phi[X] (http://en.wikipedia.org/wiki/Euler's_totient_function). Dla każdego ułamka Y/X z tej grupy, jest N/X ułamków których licznik i mianownik jest <= N i które skracają się do Y/X.

Wobec tego rozwiązanie zadania to:

1
2
3
4

long long res = n;
for(int mianownik = 2; mianownik &lt;= M; mianownik++)
        res += (long long) phi[i] * (n/i) * 2;
printf("%lld\n",res);

Dodatkowo szybkie obliczanie tablicy phi. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

//dowolny_pierwszy_dzielnik[X] po obliczeniu będzie zawierać dowolny
//dzielnik X będący liczbą pierwszą lub 0 jeśli liczba jest pierwsza.
 
void oblicz_phi_tab(int M){
        memset(dowolny_pierwszy_dzielnik, 0, sizeof(dowolny_pierwszy_dzielnik));
        memset(phi, 0, sizeof(phi));
        
        int lim = sqrt(M);
        for(int i = 2; i &lt;= lim; i++) if (dowolny_pierwszy_dzielnik[i] == 0){
                int j = i * i;
                while(j &lt;= M){
                        dowolny_pierwszy_dzielnik[j] = i;
                        j += i;
                }
        }
        
        int a, b;
        phi[1] = 1;
        for(int i = 2; i &lt;= M; i++){
                if (dowolny_pierwszy_dzielnik[i] == 0){ // i jest pierwsze
                        phi[i] = i - 1;
                }
                else{
                        a = dowolny_pierwszy_dzielnik[i];
                        b = i / dowolny_pierwszy_dzielnik[i];
                        if (b % a == 0) phi[i] = phi[b] * a;
                        else phi[i] = phi[b] * (a - 1);
                }
        }
}       
       

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com