## Editorial for DMOPC '21 Contest 5 P4 - Permutations & Primes

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: zhouzixiang2004

Note that it is not possible for there to be only one distinct difference since is not prime. Thus we can conjecture that the smallest possible number of distinct differences is . Let's try to build a permutation that uses only the differences and . One way of doing this is to repeat the pattern (repeating the differences periodically) which works whenever is a multiple of .

Time Complexity: for each test case.

From here on, we will use 0-indexing for all indices and values of as that will turn out to be more convenient.

Again, we can conjecture that the smallest possible number of distinct differences is for all that is not too small.

Let's find two distinct prime numbers and with . By Goldbach's conjecture, we expect that such and will exist whenever is even and not too small. Goldbach's conjecture is unproven and doesn't guarantee that the two primes are distinct, but it is possible to verify using a computer that such exists for all even between and . Cases where is small ( ) may need to be handled separately, and we can find an answer for these small by hand and hardcode them.

Now consider setting for all . We have that , so either (if ) or (if ) for all . Hence this sequence only has two distinct adjacent differences ( and ) as needed. Furthermore, this is a permutation since (because and are distinct primes), and this means that if , then .

If we implement this solution by sieving all the primes up to , then the time complexity is . It is also possible to obtain behaviour by trying in increasing order and checking if and are both prime (in time for each ), as we will intuitively find a good and way before checking numbers.

Time Complexity: (or behaviour) for each test case.

First, we handle the small separately, which now includes all between and .

If is even, we can do the construction as in subtask 2. Note that the above construction in fact gives a cyclic sequence with only and as adjacent differences ( or as well). Thus if is odd, we can perform the above construction for to obtain a permutation of , cyclically shift it so that , and set (in fact, if we use the exact same formula as shown above, we do not even need to do a cyclic shift as ).

Time Complexity: (or behaviour) for each test case.

Remark: The properties of the prime numbers this problem uses are:

• Goldbach's conjecture, allowing us to find primes and with or .
• Coprimeness of distinct primes, allowing the sequence to "cover" all residues modulo .