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 | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | atcoder_official | 148 |
5 | -is-this-fft- | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
10 | TheScrasse | 142 |
Название |
---|
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