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!
maybe https://codeforces.com/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
Auto comment: topic has been updated by ganesh_6 (previous revision, new revision, compare).
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.
(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
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