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;