A solution exists for the equation (\gcd(an+b, c) = 1) if and only if (\gcd(a, b, c) = 1). If (\gcd(a, b, c) > 1), the problem has no solution and (-1) is output.

Given the condition (\gcd(a, b, c) = 1), we can construct a valid (n). Let (x = \gcd(b, c)). If (x = 1), then (n = 0) satisfies (\gcd(a*0+b, c) = \gcd(b, c) = 1).

If (x > 1), we need to find (n) such that (\gcd(an+b, c) = 1). Note that since (\gcd(a, b, c)=1), it follows that (\gcd(a+b, x) = 1). Consider the expression (an+b = a(n) + b). If we can find an (n) where (\gcd(an+b, c/x) = 1), then, combined with (\gcd(an+b, x)=1), we achieve the overall goal due to the property: if (\gcd(y, p)=1) and (\gcd(y, q)=1), then (\gcd(y, pq)=1).

Observe that adding multiples of (a \cdot x) to (a+b) preserves coprimality with (x). That is, (\gcd(k \cdot a x + a + b, x) = 1) for any integer (k). Our objective reduces to finding a (k) such that: [ \gcd(k \cdot a x + a + b, , c/x) = 1 ] This is a subproblem of the original form with parameters:

• New (a' = a x)
• New (b' = a + b)
• New (c' = c / x) We solve this recursively. The recursion depth is bounded by (O(\log c)) because (x > 1), and (c) is divided by atleast 2 in each step (in practice often 1-2 levels).

Proof of Solvability for Subproblems We must verify that the condition (\gcd(a', b', c') = 1) holds for each recursive call, assuming the original (\gcd(a, b, c)=1). We prove by contradiction. Suppose a prime (p) divides (\gcd(a x, a+b, c/x)). Then (p) divides (a x) and (a+b).

• If (p) divides (x), then (p) divides (b) (since (x = \gcd(b, c))). Since (p) divides (a+b), it must also divide (a). This implies (p) divides (\gcd(a, b, c)), contradicting the initial condition.
• If (p) divides (a), then from (p) dividing (a+b), it follows that (p) divides (b). Again, (p) divides (\gcd(a, b, c)), a contradiction. Therefore, no such prime (p) exists, and the subproblem maintains the solvability condition.

Implementation

from math import gcd

def find_n(alpha, beta, gamma):
    divisor = gcd(beta, gamma)
    if divisor == 1:
        return 0
    # Recursively solve the subproblem
    sub_solution = find_n(alpha * divisor, alpha + beta, gamma // divisor)
    return sub_solution * divisor + 1

# Main processing loop
num_cases = int(input())
for _ in range(num_cases):
    A, B, C = map(int, input().split())
    if gcd(gcd(A, B), C) > 1:
        print(-1)
    else:
        print(find_n(A, B, C))

Analysis of Heuristic Enumeration Approach While the constructive method is efficient, a simple linear search from (n=0) upward also works with in typical constraints. A heuristic justification follows. Let the prime factorization of (c) have (\omega(c)) distinct primes. Suppose the minimal valid (n) is (n_{\text{min}}). For all (m < n_{\text{min}}), there exists some prime (p_m) dividing both (a m + b) and (c). Consider two consecutive values (s) and (s+t) where (t) is prime and (s+t < n_{\text{min}}). Let (p_s) and (p_{s+t}) be the corresponding primes.

• If (p_s \neq p_{s+t}), then two distinct prime factors of (c) are 'consumed'.
• If (p_s = p_{s+t} = p), then (p) divides (a(s+t)+b - (as+b) = a t). Since (\gcd(a, b, c)=1), (p) cannot divide (a) (or else it would also divide (b)). Thus, (p) must divide (t). As (t) is prime, (p = t), meaning this prime (t) itself is a factor of (c). Thus, each prime-step interval either reveals a new prime factor of (c) or confirms an existing one. Given the limited number (\omega(c) = O(\log c)) of distinct prime factors, the minimal (n_{\text{min}}) is expected to be small, often within (O(\log c)) bounds. This also supports the efficacy of randomized testing.

Simple Linear Search Implementation

from math import gcd

num_cases = int(input())
for _ in range(num_cases):
    A, B, C = map(int, input().split())
    if gcd(gcd(A, B), C) > 1:
        print(-1)
        continue
    n_val = 0
    while gcd(A * n_val + B, C) > 1:
        n_val += 1
    print(n_val)