|
|
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? |
|
|