1295D - Same GCDs

Link to the problem : https://codeforces.com/problemset/problem/1295/D

I had to see the tutorial to understand this.

$$gcd(a, m) = gcd(a + x, m)$$

Now, using Euclid's algorithm, we can say that 

$$gcd(a, b) = gcd(a - b, b)$$

So, in our case, that would be:

$$gcd(a + x, m) = gcd(a + x - m, m) = gcd(a + x - 2 \times m, m) = ...  = gcd((a + x) \% m, m)$$

Now, in the problem it's given that $0 \leq x < m$, so we can say that $a \leq a + x < a + m$, and therefore we can also say that $0 \leq (a + x)\%m < m$

So, we can assume $$Y = (a + x)\%m$$

We can say:

$$gcd(a, m) = gcd(a + x, m) = gcd(Y, m)$$

Let's say that $gcd(a, m) = G$

So $$gcd(Y, m) =  G$$

This means that G can divide both Y, and m, and there are no further common divisors (besides 1) in Y and m. This means:

$$gcd(Y / G, m / G) = 1$$

Now notice that the variable here is $Y/G$. We want it to be such that it's co-prime to $m/G$. Also notice that since $Y < m$, $Y/G < m/G$. Therefore the Euler's totient function is applicable here. More details on that : https://cp-algorithms.com/algebra/phi-function.html

So we just need to calculate the totient function for $m/G = m / gcd(a, m)$

My submission : https://codeforces.com/contest/1295/submission/240298664