Yesterday I took part in mail.ru cup round 2 and came across this problem. This is a maths problem and has tags math and number theory but from the editorial I couldn’t understand how to approach this problem…

In the comments section it was written that the question can be solved using Bezout’s identity…

“All possible shifts of Alice’s and Bobs’ pattern periods are the multiples of gcd(ta,tb).”