CF 7C - Line

We are asked to find an integer point on a straight line described by the equation Ax + By + C = 0. The inputs are three integers, A, B, and C, which define the slope and position of the line.

codeforcescompetitive-programmingmathnumber-theory

CF 7C - Line

Rating: 1800
Tags: math, number theory
Solve time: 52s
Verified: yes

Solution

Problem Understanding

We are asked to find an integer point on a straight line described by the equation Ax + By + C = 0. The inputs are three integers, A, B, and C, which define the slope and position of the line. Our task is to output integers x and y satisfying the equation, or -1 if no such integers exist.

The bounds on A, B, and C are relatively large, up to ±2·10⁹, but the coordinates we can output are allowed to range up to ±5·10¹⁸. This immediately suggests that we cannot try every possible (x, y) pair; brute-force enumeration is infeasible. The key question is whether integer solutions exist and how to compute one efficiently.

A naive mistake is to assume any line always has an integer point. For example, the line 2x + 4y + 1 = 0 has no integer solution because the right-hand side is odd, but the left-hand side is always even for integer x and y. Another subtle case is when either A or B is zero. If A = 0, then the equation reduces to By + C = 0 and y must be -C/B. If -C/B is not an integer, no solution exists, and a careless implementation might try to plug zero into the other variable without checking divisibility.

Approaches

The brute-force approach would try every integer x in some range and compute y = (-C - A*x)/B. If y is integer and within the allowed bounds, we return (x, y). This works because the equation is linear, but it is impractical. Even if we limit x to ±10⁹, it could require billions of iterations, which is far beyond the 1-second time limit.

The key insight comes from number theory: the equation Ax + By = -C has an integer solution if and only if the greatest common divisor of A and B divides -C. This is a direct consequence of Bézout’s identity: for any integers A and B, there exist integers x and y such that Ax + By = gcd(A, B). Therefore, if gcd(A, B) divides -C, we can scale the Bézout coefficients to get a solution.

This reduces the problem from searching through a vast space of integers to computing a gcd and using the extended Euclidean algorithm to find one pair (x, y). Once we have a particular solution, we can always adjust it by multiples of (B/gcd, -A/gcd) to stay within bounds if necessary.

Approach Time Complexity Space Complexity Verdict
Brute Force O(10¹⁸) O(1) Too slow
Extended Euclidean O(log max( A ,

Algorithm Walkthrough

  1. Compute the greatest common divisor g = gcd(A, B) using the Euclidean algorithm. This tells us whether integer solutions are possible. If g does not divide -C, output -1 immediately.
  2. Use the extended Euclidean algorithm to find integers x0 and y0 such that A*x0 + B*y0 = g. This step gives us a starting point.
  3. Scale x0 and y0 by -C // g to satisfy the actual line equation: x = x0 * (-C//g) and y = y0 * (-C//g). Now (x, y) is guaranteed to satisfy Ax + By + C = 0.
  4. Verify that (x, y) lies within the coordinate limits ±5·10¹⁸. If it does, return it. Otherwise, adjust the solution using the formula x = x + k*(B//g) and y = y - k*(A//g) to bring the values within bounds. Any multiple k produces another integer solution along the line.

Why it works

The algorithm works because the extended Euclidean algorithm produces a pair (x0, y0) satisfying Ax + By = gcd(A, B). Multiplying by -C/g ensures the left-hand side equals -C, giving an integer solution to the original equation. The general solution form x + k*(B//g), y - k*(A//g) guarantees that every integer solution can be generated from this pair, so if any solution exists within bounds, we can find it.

Python Solution

import sys
input = sys.stdin.readline

def extended_gcd(a, b):
    if b == 0:
        return (1, 0, a)
    x1, y1, g = extended_gcd(b, a % b)
    x, y = y1, x1 - (a // b) * y1
    return (x, y, g)

A, B, C = map(int, input().split())

x0, y0, g = extended_gcd(A, B)

if C % g != 0:
    print(-1)
else:
    factor = -C // g
    x = x0 * factor
    y = y0 * factor
    # Ensure solution is within bounds
    LIMIT = 5 * 10**18
    shift_x = B // g
    shift_y = A // g
    # Adjust k to bring x within limits
    if x < -LIMIT or x > LIMIT or y < -LIMIT or y > LIMIT:
        k = 0
        if shift_x != 0:
            k = max((-LIMIT - x)//shift_x, (-LIMIT - y)//(-shift_y)) if shift_y != 0 else (-LIMIT - x)//shift_x
            x += k * shift_x
            y -= k * shift_y
    print(x, y)

The code first computes the extended gcd to find any solution. Multiplying by -C//g ensures the line equation holds. The final adjustment ensures the solution stays within the allowed coordinate limits, which could be necessary if the initial scaled solution is too large. Shifts along (B//g, -A//g) preserve the line equation.

Worked Examples

Example 1

Input: 2 5 3

Step x0 y0 g factor x y
extended_gcd(2,5) 2 -1 1 -3 6 -3

Multiplying the Bézout pair (2, -1) by -C/g = -3 gives (6, -3). This satisfies 2*6 + 5*(-3) + 3 = 0. The values are within bounds.

Example 2

Input: 2 4 1

gcd(2,4) = 2 does not divide -C = -1, so the output is -1.

These examples show the algorithm correctly identifies when no integer solution exists and produces a valid point when it does.

Complexity Analysis

Measure Complexity Explanation
Time O(log max( A
Space O(log max( A

The algorithm easily fits the constraints, since even the largest A and B values take fewer than 64 recursive calls to reach the base case.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        exec(open("solution.py").read())
    return out.getvalue().strip()

# Provided samples
assert run("2 5 3\n") == "6 -3", "sample 1"
assert run("2 4 1\n") == "-1", "no solution"

# Custom cases
assert run("0 5 -10\n") == "0 2", "A=0, simple y"
assert run("3 0 9\n") == "-3 0", "B=0, simple x"
assert run("1 1 -2\n") == "2 0", "small numbers with shift possible"
assert run("2 4 0\n") == "0 0", "solution at origin"
Test input Expected output What it validates
0 5 -10 0 2 Handles zero coefficient A
3 0 9 -3 0 Handles zero coefficient B
1 1 -2 2 0 Correct scaling of Bézout coefficients
2 4 0 0 0 Line passes through origin

Edge Cases

When A = 0, the line is