Odd or even permutation?

Problem Statement

Given $N$ and $K$, generate the sequence $a_i := K \cdot i \,\,\, (\mathrm{mod }\,\, N)$. Let $M$ be the number of inversions¹ of the sequence $(a_0, a_1, \dots, a_{j-1})$ where $j$ is the smallest positive index such that $a_j = 0$. Determine if $M$ is odd or even. The challenge here is to design an algorithm that solves this problem quickly.

Example: if $N = 5$ and $K = 3$, then the sequence is $(0, 3, 1, 4, 2)$. Its number of inversions $M$ is $3$, which is odd.

Before reading on, I invite you to try a few more examples to get a feel for this problem. See if you can spot a pattern.

Solution

[1] The number of inversions of a sequence of numbers is the minimum number of adjacent swaps required to sort the numbers in non-decreasing order.