Codeforces Round #641 (Div. 2) problem C(Orac and LCM): An easier way to approach to the solution

Revision en4, by reyad, 2020-05-28 14:01:23

The problem requires us to find gcd({lcm({a_i, a_j}) | i < j}).

Now, for each a_i we can take a_j(where i < j) to make a pair.
So the pairs would be like: (a_i, a_i+1), (a_i, a_i+2), (a_i, a_i+3), ..., (a_i, a_i+k) // let's assume, i+k = n
and we've to find lcm of those pairs
and then gcd of those lcms. [note: we've to do this for each of a_i]

Now, let's try write the formula using gcd and lcm and in a more readable format:

gcd(lcm(u, v_1), lcm(u, v_2), lcm(u, v_2), ..., lcm(u, v_k))......(01) [note: u replaces a_i, v_x replaces a_i+x]

let's say, the result of the formula(01) is d i.e. d | {lcm(u, v_x) | 1 <= x <= k}

let's, d = (p_1 ^ r_1) * (p_2 ^ r_2) * .... * (p_h ^ r_h)

According to definition (i) for lcm: we take the max power of prime divisors between the two elements (ii) for gcd: we take the min power of prime divisors between the two elements

let's assume, d = du * dv (so, du and dv both must be found in each and every lcm pairs)
now, say, du contains the primes those are contributed from u(note: u is common in each pair)
dv contains the primes those are contributed from v_1, v_2, ...., v_k i.e. dv should be found in each of v_x(where 1 <= x <= k) or we may say dv | {v_x | 1 <= x <= k)}.

So, it can be said that,
gcd(lcm(u, v_1), lcm(u, v_2), lcm(u, v_2), ..., lcm(u, v_k)) = lcm(u, gcd(v_1, v_2, v_3, ..., v_k))...(02)

by using formula(02) we can easily find lcm of each pairs of that contains a_i, and then take gcd of those lcms:

Solution: ~~~~~ let, g[0....n-1] where g[i] denotes gcd of a[i], a[i+1], ..., a[n-1]
let, ans = 0
for i = 0...n-1:
ans = gcd(ans, lcm(a[i], g[i+1]))
print ans
~~~~~

The solution link is given here.

Tags #641 (div. 2), #math, #number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English reyad 2020-05-28 21:48:07 4
en8 English reyad 2020-05-28 14:26:11 0 (published)
en7 English reyad 2020-05-28 14:18:57 68
en6 English reyad 2020-05-28 14:13:02 41
en5 English reyad 2020-05-28 14:06:58 136
en4 English reyad 2020-05-28 14:01:23 1395
en3 English reyad 2020-05-28 13:47:25 68
en2 English reyad 2020-05-28 13:42:05 63
en1 English reyad 2020-05-28 13:39:21 1878 Initial revision (saved to drafts)