Uva 10179 – Irreducable Basic Fractions

Problem Link


Euler function  Phi (n) (sometimes denoted  Varphi (n)or { It phi} (n)) – is the amount of numbers from 1up to nprime to n. In other words, the number of properties in the interval [1; n], the greatest common divisor of which a nroot of unity.
The first few values ​​of this function ( A000010 in OEIS encyclopedia ):
  Phi (1) = 1,
  Phi (2) = 1,
  Phi (3) = 2
  Phi (4) = 2
  Phi (5) = 4.


The following three simple properties of the Euler – enough to learn how to calculate it for any number:
  • If p– prime, then  Phi (p) = p-1.
    (This is obvious, since any number, except for the prelatively easy with him.)
  • If p– simple a– positive integer, then  Phi (p ^ a) = p ^ ap ^ {a-1}.
    (Because the number of p ^ anot only relatively prime numbers of the form , which the pieces.)pk (K  in  mathcal {N})p ^ a / p = p ^ {a-1}
  • If aand bare relatively prime, then  Phi (ab) =  phi (a)  phi (b)(“multiplicative” Euler function).
    (This follows from the Chinese Remainder Theorem . Consider an arbitrary number z  le ab. denote xand ythe remainders zat aand b, respectively. then zprime to abif and only if the zprime to aand bseparately, or what is the same thing as xa one- simply aand yrelatively prime to b. Applying the Chinese remainder theorem, we see that any pair of numbers xand the number of one-to-one correspondence , and this completes the proof.)y (X  le a, ~ y  le b)z (Z  le ab)
From here you can get the Euler function for each  It nthrough its factorization (decomposition ninto prime factors)
 n = p_1 ^ {a_1}  cdot p_2 ^ {a_2}  cdot  ldots  cdot [...]
(Where all p_i– simple), then
  Phi (n) =  phi (p_1 ^ {a_1})  cdot  phi (p_2 ^ {a_2})  [...]
 = (P_1 ^ {a_1} - p_1 ^ {a_1-1})  cdot (p_2 ^ {a_2} - p_ [...]
 = N  cdot  left (1 - {1  over p_1}  right)  cdot  le [...]


The simplest code that computes the Euler function, factoring the number of elementary method for O ( sqrt n):
The key place for the calculation of the Euler function – is to find a factorization of the number n. This is achieved in a time much smaller O ( sqrt {n})

Applications of the Euler function

The most famous and important property of the Euler expressed in Euler’s theorem :
 a ^ { phi (m)}  equiv 1  pmod m,

where  It aand  It mare relatively prime.

In the particular case where the  It msimple Euler’s theorem turns into the so-called Fermat’s little theorem :
 a ^ {m-1}  equiv 1  pmod m

Solution :-


Hints :- http://e-maxx.ru/algo/euler_function and http://www.questtosolve.com/browse.php?pid=10179

Posted by Shipu Ahamed

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.