Same GCDs (Codeforces 1295D)
Tags: Math, number theory

You are given two integers $$$a$$$ and $$$m$$$. Calculate the number of integers $$$x$$$ such that $$$0 \le x < m$$$ and $$$\gcd(a, m) = \gcd(a + x, m)$$$.Note: $$$\gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$.

Input: The first line contains the single integer $$$T$$$ ($$$1 \le T \le 50$$$) — the number of test cases.Next $$$T$$$ lines contain test cases — one per line. Each line contains two integers $$$a$$$ and $$$m$$$ ($$$1 \le a < m \le 10^{10}$$$).

Output: Print $$$T$$$ integers — one per test case. For each test case print the number of appropriate $$$x$$$-s.

Note: In the first test case appropriate $$$x$$$-s are $$$[0, 1, 3, 4, 6, 7]$$$.In the second test case the only appropriate $$$x$$$ is $$$0$$$.

Sample Inputs:
3
4 9
5 10
42 9999999967

Sample Outputs:
6
1
9999999966

Solution (Python):
def primeFactor(N):
    i = 2
    ret = {}
    n = N
    mrFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:

            def findFactorRho(N):

                def gcd(a, b):
                    while b:
                        (a, b) = (b, a % b)
                    return a

                def f(x, c):
                    return (x * x + c) % N
                for c in range(1, 99):
                    (X, d, j) = ([2], 1, 0)
                    while d == 1:
                        j += 1
                        X.append(f(X[-1], c))
                        X.append(f(X[-1], c))
                        d = gcd(abs(X[2 * j] - X[j]), N)
                    if d != N:
                        if isPrimeMR(d):
                            return d
                        elif isPrimeMR(N // d):
                            return N // d
            while n > 1:
                if isPrimeMR(n):
                    (ret[n], n) = (1, 1)
                else:
                    mrFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
    if n > 1:
        ret[n] = 1
    if mrFlg > 0:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret

def isPrimeMR(n):
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False
    d = n - 1 >> 1
    while d & 1 == 0:
        d >>= 1
    L = [2, 7, 61] if n < 1 << 32 else [2, 13, 23, 1662803] if n < 1 << 40 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for a in L:
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and (y != n - 1):
            y = y * y % n
            t <<= 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True

def gcd(a, b):
    while b:
        (a, b) = (b, a % b)
    return a
T = int(input())
for _ in range(T):
    (a, m) = map(int, input().split())
    g = gcd(a, m)
    n = m // g
    pf = primeFactor(n)
    ans = 1
    for p in pf:
        ans *= (p - 1) * p ** (pf[p] - 1)
    print(ans)

Solution (Python):
def primeFactor(N):
    i = 2
    ret = {}
    n = N
    mrFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k:
            ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:

            def findFactorRho(N):

                def gcd(a, b):
                    while b:
                        (a, b) = (b, a % b)
                    return a

                def f(x, c):
                    return (x * x + c) % N
                for c in range(1, 99):
                    (X, d, j) = ([2], 1, 0)
                    while d == 1:
                        j += 1
                        X.append(f(X[-1], c))
                        X.append(f(X[-1], c))
                        d = gcd(abs(X[2 * j] - X[j]), N)
                    if d != N:
                        if isPrimeMR(d):
                            return d
                        elif isPrimeMR(N // d):
                            return N // d
            while n > 1:
                if isPrimeMR(n):
                    (ret[n], n) = (1, 1)
                else:
                    mrFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
    if n > 1:
        ret[n] = 1
    if mrFlg > 0:
        ret = {x: ret[x] for x in sorted(ret)}
    return ret

def isPrimeMR(n):
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False
    d = n - 1 >> 1
    while d & 1 == 0:
        d >>= 1
    L = [2, 7, 61] if n < 1 << 32 else [2, 13, 23, 1662803] if n < 1 << 40 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for a in L:
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and (y != n - 1):
            y = y * y % n
            t <<= 1
        if y != n - 1 and t & 1 == 0:
            return False
    return True

def gcd(a, b):
    while b:
        (a, b) = (b, a % b)
    return a
T = int(input())
for _ in range(T):
    (a, m) = map(int, input().split())
    g = gcd(a, m)
    n = m // g
    pf = primeFactor(n)
    ans = 1
    for p in pf:
        ans *= (p - 1) * p ** (pf[p] - 1)
    print(ans)

Solution (Python):
""""""
import math

def prime_factors(n):
    assert n > 0
    if n == 1:
        return [1]
    f = []
    while n % 2 == 0:
        f.append(2)
        n /= 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        while n % i == 0:
            f.append(i)
            n /= i
    if n > 1:
        f.append(int(n))
    return f

def factors_in(i, e, p):
    d = 0
    n = i + (p - i % p)
    while n >= i and n < e:
        d += 1
        n += p
    return d

def solve_slow():
    (a, m) = map(int, input().split())
    gcd = math.gcd(a, m)
    sol = 0
    for x in range(m):
        if gcd == math.gcd(a + x, m):
            sol += 1
    print(sol)

def eulers_phi_fun(n):
    f = prime_factors(n)
    val = n
    for i in set(f):
        val *= 1 - 1 / i
    return int(val)

def solve():
    (a, m) = map(int, input().split())
    gcd = math.gcd(a, m)
    n = m / gcd
    phi = eulers_phi_fun(n)
    print(phi)

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()