Mathematics Asked on January 3, 2022
LCM can be upto or greater than $10^{50}$.
$k$ and $m$ are upto $10^9$.
My current approach is
This is working but takes a long time in finding LCM using GCD.
Is there any other way?
Hint: there is no need to actually calculate $LCM(a_1,ldots,a_n)$. We only have to find $LCM bmod m$. Instead calculate $d=GCD(a_1,ldots,a_n,m)$.
Let $x = LCM(a_1,ldots,a_n) bmod m$. This means that $x = LCM - ell m$ for some integer $ell$.
The right hand side is divisible by $d$, therefore $x$ is divisible by $d$ as well.
So we have $x = dcdot(frac{LCM}d - ell frac md)$ and we can write: $$x=dcdotleft(frac{LCM}{d} bmod frac mdright) = dcdotleft(LCM(frac{a_1}d,ldots,frac{a_n}d)bmod frac mdright).$$
Answered by Klaas van Aarsen on January 3, 2022
0 Asked on November 27, 2020 by jskattt797
2 Asked on November 27, 2020 by iv_
1 Asked on November 27, 2020 by daniels-krimans
1 Asked on November 27, 2020 by jos-pedro-ferreira
1 Asked on November 27, 2020 by avir_12
2 Asked on November 27, 2020 by v-elizabeth
1 Asked on November 27, 2020 by harshatech2012
first order logic formal proofs logic predicate logic satisfiability
1 Asked on November 26, 2020 by luyw
2 Asked on November 26, 2020 by mathfun
1 Asked on November 26, 2020 by diego-lima
1 Asked on November 26, 2020 by simon
0 Asked on November 26, 2020 by godorgovern
1 Asked on November 26, 2020 by financial_physician
2 Asked on November 26, 2020 by user823011
1 Asked on November 25, 2020 by billy-rubina
3 Asked on November 24, 2020 by user801303
1 Asked on November 23, 2020
3 Asked on November 22, 2020 by slave-of-christ
combinatorics diophantine equations elementary number theory integers
Get help from others!
Recent Answers
Recent Questions
© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP