I am solving the problem https://codeforces.me/contest/1579/problem/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.me/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!
maybe https://codeforces.me/contest/1579/problem/F
?
I wanted to say that your link is wrong
Thanks link is fixed. Would be happy if i get the reply to my query?
Sorry but I can't explain it
When you shift $$$k$$$ times by $$$d$$$, it's the same as shifting by $$$k \cdot d$$$. For any $$$i$$$, shifting by $$$i$$$ and by $$$i+N$$$ is the same. That means increasing/decreasing $$$k$$$ by $$$N/g$$$ ($$$g$$$ is your gcd) doesn't do anything, $$$k \cdot d \equiv (k + N/g) \cdot d = k \cdot d + N \cdot (d/g)$$$ because $$$g$$$ divides $$$d$$$ so the second term is a multiple of $$$N$$$.
You apply it in a more specific way in the problem, of course.