Editorial for COCI '11 Contest 2 #3 Zadaća

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The greatest common divisor of two integers can be defined as the product of their common prime factors, as follows:

$\displaystyle \begin{align*} A &= p_1^{a_1} \times p_2^{a_2} \times \dots \times p_n^{a_n} \\ B &= p_1^{b_1} \times p_2^{b_2} \times \dots \times p_n^{b_n} \\ \gcd(A, B) &= p_1^{\min(a_1, b_1)} \times p_2^{\min(a_2, b_2)} \times \dots \times p_n^{\min(a_n, b_n)} \end{align*}$ $\begin{aligned} A & = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times \dots \times p_{n}^{a_{n}} \\ B & = p_{1}^{b_{1}} \times p_{2}^{b_{2}} \times \dots \times p_{n}^{b_{n}} \\ gcd (A, B) & = p_{1}^{min (a_{1}, b_{1})} \times p_{2}^{min (a_{2}, b_{2})} \times \dots \times p_{n}^{min (a_{n}, b_{n})} \end{aligned}$

where $p_1, \dots, p_n$ $p_{1}, \dots, p_{n}$ are the prime factors and $a_1, \dots, a_n$ $a_{1}, \dots, a_{n}$ , $b_1, \dots, b_n$ $b_{1}, \dots, b_{n}$ are corresponding exponents.

We can get the factorization of large numbers $A$ $A$ and $B$ $B$ by factorizing every of their given factors and summing the prime number exponents over some prime in all factorizations. The next step is computing the GCD using the expression given above.

An alternative solution would be to find GCD of all pairs of numbers $A_i, B_j$ $A_{i}, B_{j}$ and it to the result (multiply), and divide the numbers $A_i, B_j$ $A_{i}, B_{j}$ with the same number to prevent adding it to the result several times (in the next iterations).

Comments

There are no comments at the moment.