hrishabhpatel09's blog

By hrishabhpatel09, history, 11 months ago, In English

I have submitted a solution for this problem 1349A - Orac and LCM and got AC wondering if this is really a property?

Submission: 321223203

i figured out that i can write:

GCD( lcm(a1,a2), lcm(a1,a3), lcm(a1,a4) ... lcm(a1,an)) = LCM(a1, GCD(a2,a3,a4,a5,...an))

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

»
11 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

yeah this seems right; if d | a1 and d does not divide all of a2,a3..., then a1 is present in each term of the GCD and thus is in the LHS. furthermore, d | a1 means that d is present in a1. if d divides all of a1l of a1,a2,a3,...an, then d is clearly present on both sides for the same reason.

if d does not divide a1 but d | a2,a3,a4,...an, then d again divides every term in the left GCD so, d is present in the LHS. furthermore, d is present in the RHS as it is in the right GCD term as well.

if d does not divide a1 and does not divide all of a2,a3,a4, then d is not present in every term in the left GCD, so it does not appear in the LHS. furthermore; it does not appear in the RHS as it divides neither a1 nor all of a2,a3,a4...an.

»
11 months ago, hide # |
Rev. 2  
Vote: I like it +19 Vote: I do not like it

Show $$$\min(\max(a_1,a_2),\max(a_1,a_3),\dots,\max(a_1,a_n)))=\max(a_1,\min(a_2,\dots,a_n))$$$.

If $$$a_1 \gt \min$$$, all of them smaller than $$$a_1$$$ become $$$a_1$$$, and $$$\min$$$ becomes $$$a_1$$$. Thus, result is $$$a_1$$$.

If $$$a_1 \lt \min$$$, then $$$\max$$$ is not affected and result is $$$\min(a_2,\dots,a_n)$$$.

Now, same property holds for $$$\gcd$$$ and $$$\operatorname{lcm}$$$ as they become $$$\min$$$ and $$$\max$$$ on each exponent.

$$$\blacksquare$$$