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 | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 151 |
Название |
---|
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