ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 2130. Alice + Bob

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
Posted by soldSoulToTheGame 27 May 2024 15:51
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