Аркадная раскладка: взаимно простые и не на своих местах

В школьном игровом клубе есть ряд из n автоматов (позиции пронумерованы от 1 до n) и n карточек-пропусков (карточки тоже пронумерованы от 1 до n).

Тренер придумал «честную раскладку»:

• на позиции i нельзя класть карточку i (никто не играет на «своём» автомате);
• номер позиции i и номер карточки на ней должны быть взаимно простыми.

Нужно вывести лексикографически минимальную подходящую перестановку карточек.

Перестановка p1, p2, ..., pn лексикографически меньше q1, q2, ..., qn, если в первом месте, где они отличаются, значение в p меньше.

Гарантируется, что решение существует.

Формат ввода Одно целое число n.

Формат вывода Выведите n целых чисел — искомую перестановку p1..pn.

Ограничения

• 2 ≤ n ≤ 2000

Пример Ввод:

3

Вывод:

2 3 1

Ключевое наблюдение: соседние числа всегда взаимно просты, то есть gcd(i, i+1) = 1. Значит, если на позиции i поставить i+1 (а на i+1 поставить i), то обе позиции сразу выполняют условия: карточка не на своём месте и НОД равен 1.

Почему это даёт лексикографический минимум: на позиции 1 нельзя ставить 1, значит минимально возможное значение — 2, и оно подходит (НОД(1,2)=1). После того как мы выбрали 2, карточку 1 где-то надо разместить, и самый «дешёвый» способ не испортить первые элементы — просто сделать обмен (1,2). Тот же аргумент повторяется для (3,4), (5,6)…

План:

• Идём парами: для каждого нечётного i ставим p[i]=i+1, p[i+1]=i.
• Если n чётное — пар хватает до конца.
• Если n нечётное — после пар останутся последние 3 позиции n-2, n-1, n.
• Ставим цикл: p[n-2]=n-1, p[n-1]=n, p[n]=n-2.
• Проверка НОД: первые два — соседи, а gcd(n, n-2)=gcd(n,2)=1, потому что n нечётное.

Сложность: O(n) по времени и O(n) по памяти.

Частая грабля: при нечётном n просто «соседние свапы» оставят p[n]=n (фиксированная точка), это запрещено — поэтому и нужен именно 3-цикл в конце.