Codeforces 109 1B / 2D - Colliders

Link to statement
I kind of solved this during the contest, I just made the absurdly wrong assumption that I only needed prime factors up to sqrt(100000), this is completely wrong and stupid. A prime factor can be up to (N/2). I also did something complicated to get the number of the conflicting collider (I knew that only a collider can use a prime factor, but I forgot about that when making this operation). I have no idea why this happened.

I find this problem to share a lot of traits to the topcoder problem from the round just after. The same logic to ensure that the numbers are co-prime is very useful in both problems.

n and m can be sort of large, up to 100000. It is best to make the algorithms better than O(n*m), just for example. The following solution will work in O(m * sqrt(n)) time, so that's quite fine.

First of all, co-prime numbers. Although gcd(a,b) = 1 is the definition used in the statement, it really pays to see the problem as (No two colliders can share a prime factor). You can be sure that the maximum number of distinct prime factors a number can have is O(log(n)) (It is actually better than that). For example, try 2*3*5*7*11*13*17 , that is already larger than 100000. Thus you can assume a number will never have more than 7 distinct prime factors.

So, the algorithm is rather simple, when considering that. Assume that you have a list of all the prime factors of each of the numbers from 1 to 100000. That is an array [6][100001]. Which is perfectly fine for the memory limit. Then, let's say that you have an array that for each prime factor, sets whether it is currently in use by a collider (A collider that is a multiple of that prime exists) or not. The solution becomes an easy simulation: When turning on a collider, set the array to true for all of its prime factors. When verifying if you can turn a collider on, see for each of its prime factors if the array is already true or not. When turning a collider off, set the boolean values of its prime factors to false (This works because only one collider at the same time can be a multiple of a prime factor).

We forgot about something, the conflict message requires you to say the number of a collider that conflicts with the request. That is easy, instead of just setting leaving true or false to the array that determines used prime factors. Leave the number of the collider that uses it or -1 if no collider uses it.

Prime factors quickly
The previous solution is correct and works in O(m * log(n) ) time but it assumes we already have a list of the prime factors for each number. We need to get this list quickly.

Looping through each of the n numbers, and factorizing them, may work in time. Maybe 100000 * sqrt(100000) is fine. maybe.... If you want something faster, here is a trick that uses a slight modification to the Sieve of Eratosthenes. In the normal sieve, you mark the numbers you find to be composite as such. However, think of it, whenever you mark a composite number as false for the first time, you are doing so because you have just found the first prime factor of the number. Thus, you can modify the Sieve of Eratosthenes slightly to make it return a list of the first prime factor for each number from 2 to n (For a prime number, its first and only prime factor is itself). You can then use this list to quickly factorize any number from 2 to n:
- Extract first prime factor : q
- Divide x by q until x is no longer a multiple of x.
- Use the new value of x to find the next prime factor, and repeat until x is 1.