Skip to content

[CodeChef] Starters 73 — Find an Integer: add X + Y and both conditions become one

Published 5 October 2026

Problem: CodeChef — Find an integer (Starters 73, difficulty 1714).

Given \(1 \le X, Y \le 10^9\), find any \(N\) with \(1 \le N \le 10^{18}\) such that \(X \mid N + Y\) and \(Y \mid N + X\).

Background: the Chinese remainder theorem

The first thing I noticed was that “I know \(N \bmod x\) and \(N \bmod y\), find \(N\)” is a CRT problem. It asks for \(N\) with

\[N \equiv a \pmod{x}, \qquad N \equiv b \pmod{y}.\]

With \(g = \gcd(x, y)\):

  • A solution exists iff \(a \equiv b \pmod g\). \(N \bmod g\) can be read off from either congruence, so the two readings have to agree.
  • When it exists, it’s unique mod \(\operatorname{lcm}(x, y)\). If \(N_1\) and \(N_2\) both work, \(x\) and \(y\) both divide \(N_1 - N_2\), so \(\operatorname{lcm}(x, y)\) does too. The solutions are \(N_0, N_0 + L, N_0 + 2L, \dots\) with \(L = \operatorname{lcm}(x, y)\).

To compute \(N_0\), write \(N = a + xk\) and substitute into the second congruence: \(xk \equiv b - a \pmod y\). Extended Euclid gives \(u\) with \(ux + vy = g\). Dividing through by \(g\), \(u \cdot \frac{x}{g} \equiv 1 \pmod{\frac{y}{g}}\), so \(u\) inverts \(\frac{x}{g}\) and

\[k \equiv \frac{b - a}{g} \cdot u \pmod{\frac{y}{g}}.\]
def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y


def crt(a, x, b, y):
    """Smallest positive N with N % x == a and N % y == b, or None."""
    g, u, _ = ext_gcd(x, y)
    if (b - a) % g:
        return None
    lcm = x // g * y
    n = (a + x * ((b - a) // g * u % (y // g))) % lcm
    return n if n > 0 else lcm

(Python’s % is already non-negative for a positive modulus. In C++ you’d have to normalise it.)

Applying it here

The two conditions are \(N \equiv -Y \pmod X\) and \(N \equiv -X \pmod Y\), so crt((-Y) % X, X, (-X) % Y, Y) solves it. The existence check always passes: \(g\) divides both \(X\) and \(Y\), so \(-Y \equiv 0 \equiv -X \pmod g\). That’s why the statement can promise an answer.

The trick: shift by X + Y

There’s no need for extended Euclid here. Adding \(X + Y\) to \(N\) turns both conditions into the same one:

  • \(X \mid N + Y \iff X \mid N + Y + X\)
  • \(Y \mid N + X \iff Y \mid N + X + Y\)

So \(N\) is awesome iff \(X\) and \(Y\) both divide \(N + X + Y\), which means \(\operatorname{lcm}(X, Y) \mid N + X + Y\). Every answer has the form

\[N = k \cdot \operatorname{lcm}(X, Y) - X - Y.\]

This is the CRT family from above, with \(N_0 + X + Y\) landing on a multiple of \(L\). \(XY\) is a multiple of the lcm, so \(N = XY - X - Y\) is one member, and it checks out directly: \(N + Y = X(Y - 1)\) and \(N + X = Y(X - 1)\).

\(XY - X - Y = (X - 1)(Y - 1) - 1\) is \(\le 0\) only when \(X = 1\) or \(Y = 1\). In that case I keep adding the lcm until it’s positive. It stays below \(XY \le 10^{18}\).

Where I went wrong

My first submission printed \(1\) whenever \(XY - X - Y \le 0\), assuming everything works when \(X\) or \(Y\) is \(1\). That’s only true when both are \(1\). With \(X = 1, Y = 3\), \(N = 1\) gives \(N + X = 2\), which \(3\) doesn’t divide. The fallback has to stay inside the family, so it adds the lcm instead of jumping to \(1\). That got 25/100 before the fix.

Code

\(O(\log)\) per test for the lcm. Checked against brute force for all \(X, Y < 40\).

import math

t = int(input())
for _ in range(t):
    x, y = map(int, input().split())
    n = x * y - x - y
    lcm = math.lcm(x, y)
    while n <= 0:
        n += lcm

    print(n)

For the first sample (\(18, 42\)) this prints \(696\). The sample prints \(192\), and the smallest answer is \(66 = 126 - 18 - 42\). All three are in the same family mod \(\operatorname{lcm} = 126\).