reyad's blog

By reyad, history, 5 months ago, In English

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_3), ..., lcm(u, v_k))....(formula-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 write, 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 not contributed from u, so dv must be found as a divisor 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_3), .., lcm(u, v_k)) = lcm(u, gcd(v_1, v_2, v_3, ..., v_k))...(formula-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(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.

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it