### ganesh_6's blog

By ganesh_6, history, 9 months ago,

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!

• +2

 » 9 months ago, # |   0
•  » » 9 months ago, # ^ |   0 ?
•  » » » 9 months ago, # ^ |   0 I wanted to say that your link is wrong
•  » » » » 9 months ago, # ^ |   +1 Thanks link is fixed. Would be happy if i get the reply to my query?
•  » » » » » 9 months ago, # ^ |   0 Sorry but I can't explain it
 » 9 months ago, # |   0 Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).
 » 9 months ago, # |   +8 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.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 (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 nThanks 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
 » 2 months ago, # |   0 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