|
|
Show all threads Hide all threads Show all messages Hide all messages | How come there are solutions that are 0.015 sec and less than 0.1 sec | Sergey | 2130. Alice + Bob | 27 May 2024 15:51 | 2 | my solution is the following: start with least common multiple = 1 make char array of 1000 000 to track forbidden divisors let div be the divisor and ans the answer if ans == 1 make new lcm of the previous lcm and current divisor. if it is over 10^12 - fail. find all the divisors of div, check that they are not forbidden in the forbidden array if ans == 0 - check if lcm is divisible by the divisor and fail if it is.
complexitiy O(n * sqrt(1000000)) (sqrt from the "find all divisors) my solution gets 0.5 sec (using cin,cout with tie(null)) what is the solution that gets less than 0.1 sec? Is there any hint? no need to find all divisors. u can just use lcm and mod operations. i can send you easy solution if u r still interested |
|
|
|