Same GCD?

Find the number of x that satisfies $ gcd(a, m) = gcd(a + x, m) $ where $ 0 <= x < m $. For example, if $ a = 4 $ and $ m = 9 $, there would be 6 $x$ which are $0, 1, 3, 4, 6, 7$. From Euclidean algorithm, we know that $ gcd(a, b) = gcd(a \bmod b, b) $. For example, if $ a = 4 $ and $ b = 8 $, we know that $ gcd(12, 8) = gcd(12 \bmod 8, 8)$, in this case, which is $4$. Back to our question, we know that $ 0 <= x < m $, which means that the range of $ a + x $ would be $ a .. m + a $, it can be divided by $ m $. Let $ k $ be $ (a + x) \bmod m $, the range of $ k $ is $ 0 .. m $. Now we can rewrite it to $ gcd(a, m) = gcd(k, m) $. Let's say $ gcd(a, m) = gcd(k, m) = g $, it then can be rewritten as $ gcd(\frac{k}{g}, \frac{m}{g}) = 1 $. In this case, we can use Euler's totient function to find out how many numbers from $ 1 $ to $ \frac{k}{g} $ are co-prime to $ \frac{k}{g} $. The function is defined as $$ \varphi(n) = n \displaystyle \prod_{n= p | n}^{} (1 - \frac{1}{p}) $$ For example, for $\varphi(36)$, it can be factoralized as $\varphi(2^2 * 3^2)$ = $36 * (1 - \frac{1}{2}) * (1 - \frac{1}{3}) = 12 $. Those 12 numbers are $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31$ and $ 35$. Here's the implementation of Euler's totient function in C++. ``` long long phi(long long n) { long long result = n; for (long long i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) n /= i; result -= result / i; } } if (n > 1) result -= result / n; return result; } ``` Therefore, back to our question, the solution is relatively simple. ``` long long a, m; cin >> a >> m; cout << phi(m / gcd(a, m)) << endl; ```