ganesh_6's blog

Gcd(n, d) is the total number of cyclic sequences formed by shifting array by d everytime.
By ganesh_6, history, 3 years ago, In English

I am solving the problem https://mirror.codeforces.com/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://mirror.codeforces.com/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!

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

maybe https://mirror.codeforces.com/contest/1579/problem/F

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like 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.

→ Reply