Editorial for COCI '22 Contest 1 #4 Iksevi


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We can ignore the left and bottom walls, which allows us to consider points with negative coordinates without changing the answer. That way, every point which is on a tile's corner is some tile's top corner, some tile's left corner, some tile's bottom corner and some tile's right corner. Without loss of generality, let's consider the points which are some tile's top corner. Let's divide the tiles into even and odd rows. If the length of the diagonal in millimeters is 2k where k is a natural number, the center of the tiles in even rows is in points (2ak, 2bk) for all integers a and b, so their top corner is in points (2ak, (2b+1)k) for all integers a and b. The center of the tiles in odd rows is then in points ((2a+1)k, (2b+1)k) for all integers a and b, so their top corner is in points ((2a+1)k, (2b+2)k) for all integers a and b.

For the first subtask, it's enough to precompute all possible tiles' top corner by considering all possibilities of a, b, and k, and for each query we can easily answer how many times that point was a top corner.

For the second subtask, notice that the conditions written in the first paragraph require either x to be equal to k multiplied by an odd number and y to be equal to k multiplied by an even number, or for x to be equal to k multiplied by an even number and y to be equal to k multiplied by an odd number. From there we can easily see that x and y must be divisible by k, so we can solve the second subtask by checking the condition for all k which are divisors of both x and y, i.e. all k which are divisors of \gcd(x, y).

For the third subtask, call the GCD of x and y g. A necessary condition for a fixed k can be further simplified to k being a divisor of g and \frac x k and \frac y k having a different parity. Let \frac g k = h, \frac x g = x', and \frac y g = y'. Then h is a divisor of g, \frac x k = hx' and \frac y k = hy'. If x' and y' have the same parity, multiplying them with the same number isn't going to change that, so the answer is 0. If they don't, then multiplying them with the same even number will change that (both will become even), and multiplying them with the same odd number won't (both of their parities will remain unchanged). Therefore, we want to find the number of natural numbers h which are divisors of g and which are odd, which is the number of odd divisors of g. Before answering the queries, we can use Eratosthenes's sieve to precompute the number of odd divisors of all numbers between 1 and 10^7 to easily answer all the queries.


Comments

There are no comments at the moment.