How come there are solutions that are 0.015 sec and less than 0.1 sec

Posted by

Sergey 18 Jan 2020 20:35

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?

Re: How come there are solutions that are 0.015 sec and less than 0.1 sec

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