Line

Key observation

The line equation

$$Ax+By+C=0$$

is really the linear Diophantine equation

$$Ax+By=-C.$$

So this is not geometry. It is Bézout wearing a fake mustache.

Let

$$g=\gcd(|A|,|B|).$$

For any integers $x,y$, both $A$ and $B$ are divisible by $g$, so $Ax+By$ is also divisible by $g$. Therefore a necessary condition is

$$g\mid (-C),$$

which is the same as $g\mid C$.

Bézout's identity says this condition is also sufficient: there exist integers $u,v$ such that

$$Au+Bv=g.$$

Then multiplying both sides by

$$k=\frac{-C}{g}$$

gives

$$A(uk)+B(vk)=-C.$$

So one valid answer is

$$x=uk,\qquad y=vk.$$

Finding $u,v$

Use the extended Euclidean algorithm. It naturally gives coefficients for nonnegative inputs:

$$|A|p+|B|q=g.$$

Then fix signs:

• if $A<0$, replace $p$ by $-p$;
• if $B<0$, replace $q$ by $-q$.

After that,

$$Ap+Bq=g.$$

Finally multiply by $-C/g$.

What about the huge coordinate bound?

The problem asks for coordinates between $-5\cdot 10^{18}$ and $5\cdot 10^{18}$. Looks scary, but it is basically a neon sign saying use long long.

For non-degenerate cases, extended Euclid gives coefficients with size roughly bounded by the opposite coefficient divided by $g$:

$$|p|\le \frac{|B|}{g},\qquad |q|\le \frac{|A|}{g}.$$

Since

$$|A|,|B|,|C|\le 2\cdot 10^9,$$

we get

$$|x|=\left|p\cdot \frac{-C}{g}\right|\le \frac{|B||C|}{g^2}\le 4\cdot 10^{18}<5\cdot 10^{18},$$

and similarly for $y$. If $A=0$ or $B=0$, the solution is even smaller. So the direct Bézout solution is safe.

Complexity

Extended Euclid runs in

$$O(\log \max(|A|,|B|))$$

time. Memory usage is $O(\log \max(|A|,|B|))$ due to recursion, which is tiny here.