Editorial for COCI '22 Contest 1 #4 Iksevi
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 where is a natural number, the center of the tiles in even rows is in points for all integers and , so their top corner is in points for all integers and . The center of the tiles in odd rows is then in points for all integers and , so their top corner is in points for all integers and .
For the first subtask, it's enough to precompute all possible tiles' top corner by considering all possibilities of , , and , 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 to be equal to multiplied by an odd number and to be equal to multiplied by an even number, or for to be equal to multiplied by an even number and to be equal to multiplied by an odd number. From there we can easily see that and must be divisible by , so we can solve the second subtask by checking the condition for all which are divisors of both and , i.e. all which are divisors of .
For the third subtask, call the GCD of and . A necessary condition for a fixed can be further simplified to being a divisor of and and having a different parity. Let , , and . Then is a divisor of , and . If and have the same parity, multiplying them with the same number isn't going to change that, so the answer is . 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 which are divisors of and which are odd, which is the number of odd divisors of . Before answering the queries, we can use Eratosthenes's sieve to precompute the number of odd divisors of all numbers between and to easily answer all the queries.
Comments