suppose we are given N numbers a1,a2,a3....aN. Now how to write a program which calculates the Lcm of these numbers.....
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Название |
---|
lcm(a1,a2) = a1 * a2 / gcd(a1,a2).
lcm(a1,a2,a3) = lcm( lcm(a1,a2) , a3).
And then continue this process for all numbers.
You can calculate their GCD and use this formula: LCM(a1,...,aN)*GCD(a1,...,aN) = a1*a2*...*aN
UPD: Oh, sorry it's really incorrect.
lcm(2, 2, 2) * gcd(2, 2, 2) != 2*2*2
This formula isn't correct. For example, a1 = 2, a2 = 4, a3 = 5. LCM(a1,a2,a3) = 20, GCD(a1,a2,a3) = 1, a1*a2*a3 = 40. And LCM(a1,a2,a3) * GCD(a1,a2,a3) != a1*a2*a3.
lcm(a,b) = a*b/gcd(a,b)
lcm(a1,a2,...an) = lcm(a1,lcm(a2,lcm(a3,lcm(... , an))))
i have used the same concept.... for calculating the lcm of first 20 natural numbers my code is as follows... but the answer is not coming correct
Integer overflow while calculating a*b. Use a/gcd(a,b)*b instead.
but an int can store upto 2X10^9 then how can overflow take place..
lcm(2..19) = 232792560
232792560*20 > 4e9.
thanks a lot Hohol i finally got it right.. by the way i want to tell u that i have suffered a lot due to integer overflows... how to improve my mistakes for overflows??? can u suggest me something
Every time you multiple think about maximum value. cast it to int64, if you need
this is really helpful