Блог пользователя hrishabhpatel09

Автор hrishabhpatel09, история, 12 месяцев назад, По-английски

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))

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
12 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +19 Проголосовать: не нравится

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$$$