Codeforces 1295D Same GCDs - Problem Statement

Given $a$ and $m$, count integers $x$ with $0 \le x < m$ such that $\gcd(a, m) = \gcd(a + x, m)$.

Constraints: $a, m \le 10^{10}$. The large values mean you can't iterate through all $x$.

This problem connects GCD properties to Euler's totient function.