I am solving the problem https://codeforces.net/contest/1579/probleml/F. Although I got the idea to solve it, I could not get the mathematical formula or intuition that the number of cyclic sequences formed can be gcd(a, b).

From the editorial https://codeforces.net/blog/entry/95447, I came to know that "Note that by shifts of d the array splits into gcd(n, d) cyclic sequences of this kind, each of length n/gcd(n, d)".

Can anyone explain the mathematical intuition or provide some explanation for this formula? Thanks in advance!