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, 9 months ago, In English

I am solving the problem https://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://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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).

→ Reply
»
9 months 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
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    (i+k*d)%n = (i+n+k*d)%n

    g = gcd(n, d) k+/-x*n/g => (i+n+k*d+x*n*d/g)%n = (i+k*d)%n since g can divide both d and n

    Thanks a ton! I can bolster this by writing a ton of examples and executing them.

    gcd(n, d) => divides both n and d so Think of it like two sticks of length n and length d which are in a curved shape and can fit in a circle. For example, n=6 and d=4. gcd(n, d)=2 which shows that sticks starting at 0, 1 are congruent to (i+gcd(n, d))%n.

    To know the length, it's a normal math n/gcd(n, d).

    Another example, n=5 and d=2 which are coprime so 0 is the only position to start and length of such sequence will be n.

    Another example, n=6 and d=3 d can divide n completely so d is the gcd and the number of sequences starting at 0, 1, 2 i.e; 3 sequences and length of each is 6/3 = 2.

    If we multiply the a sequence starting from certain point in a sequence modulo n will come to the same position where you started, that is the meaning of ((k+N/g) * d )%n

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is taken from a concept in group theory:

I just realized that the n/gcd(n, d) is actually the order of the subgroup generated by (a^d) where the main group has an order n. If we consider the main group as a^0=e, a^1, a^2, ... a^n. Then a^d represents the rotation of the main group generated by to the right by d. If we shift an array to right by n represented as a^n then we get the same array which is the identity element of a group a, e is the identity element.

So in the problem if we rotate the array everytime by d we get elements generated by a^d namely (a^d), (a^2d), a^3d, ... this continues until we get the same state i.e; where we started which is our identity element. So according to group theory, it has an order equal to n/gcd(n, d) and number of such unique subgroups are gcd(n, d). Here order refers to length of cyclic subgroup formed.

You can actually look at proof of this here: https://www.youtube.com/watch?v=3mnwupWDznE

→ Reply