## Editorial for Yet Another Contest 7 P2 - Coprime Grid

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.

Author: Josh

Note that there are many possible constructions which are not illustrated in this editorial.

Observe that every integer is coprime with both and . It would therefore be useful to have consecutive integers in adjacent cells. This motivates a 'snake' pattern, where an example is shown for :

 1  2  3  4  5
10  9  8  7  6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25

This grid is coprime because:

• is coprime with all integers, and so is coprime with the two integers adjacent to it.
• is adjacent to and , for all .
• is adjacent to and , which are both coprime with it. Note that and do not share any prime factors, so and must also have no prime factors in common.

Time complexity:

Our construction from subtask 1 does not always work because is not always coprime with . It's possible that is coprime with neither nor , so snaking vertically rather than horizontally does not work either. Instead, we can make a simple modification to our snake: we snake from to , and place in the remaining cell. For example, when and , our construction looks like:

 2  3  4  5  6  7
13 12 11 10  9  8
14 15 16 17 18 19
25 24 23 22 21 20
26 27 28 29 30  1

This grid is coprime because:

• is coprime with all integers, and so is coprime with the two integers adjacent to it.
• is adjacent to and , both of which are odd.
• is adjacent to and , for all .
• is adjacent to and , which are both coprime with it.

There is an alternate construction where we change the path that the snake takes, such that ends up next to either or . Any such grid would be coprime because:

• is coprime with all integers, and so is coprime with the two integers adjacent to it.
• is adjacent to and , for all .
• is adjacent to , and either or , which are both coprime with it. We can show that if is next to , it is coprime with it; if we checkerboard the grid, alternating black and white cells, we see that integers of the same parity are in the same colour of cell. Since and would be in different coloured cells, they must have opposite parities, so is odd and therefore coprime with .

Time complexity: