Overview

This is a problem of finding the least common multiple (LCM) of \(N\) positive rational numbers \(T_1, T_2, \ldots, T_N\) (given as irreducible fractions) as an irreducible fraction.

Discussion

From Integer LCM to Rational Number LCM

The least common multiple of integers is familiar, but how do we compute the LCM of rational numbers?

First, let’s confirm the definition. A positive rational number \(L\) is a common multiple of \(T_1, T_2, \ldots, T_N\) if \(\frac{L}{T_i}\) is a positive integer for all \(i\). The smallest such value is the LCM.

Key Formula

For two rational numbers expressed as irreducible fractions \(\frac{a}{b}\) and \(\frac{c}{d}\) (where \(\gcd(a,b)=1\), \(\gcd(c,d)=1\)), the following formula holds:

\[\mathrm{lcm}\!\left(\frac{a}{b},\, \frac{c}{d}\right) = \frac{\mathrm{lcm}(a, c)}{\gcd(b, d)}\]

Intuitive Understanding of the Formula

By taking the LCM of the numerators, we ensure the result is a “multiple of both numerators,” and by taking the GCD of the denominators, we maintain the “largest denominator that is divisible by both denominators.”

Verification with Concrete Examples

• \(\mathrm{lcm}\!\left(\frac{1}{2},\, \frac{1}{3}\right) = \frac{\mathrm{lcm}(1,1)}{\gcd(2,3)} = \frac{1}{1} = 1\)
  • Verification: \(\frac{1}{1/2} = 2\) ✓, \(\frac{1}{1/3} = 3\) ✓
• \(\mathrm{lcm}\!\left(\frac{2}{3},\, \frac{4}{5}\right) = \frac{\mathrm{lcm}(2,4)}{\gcd(3,5)} = \frac{4}{1} = 4\)
  • Verification: \(\frac{4}{2/3} = 6\) ✓, \(\frac{4}{4/5} = 5\) ✓

Extension to N Values

Since LCM is associative, we can compute the overall LCM by taking the LCM of two values at a time from left to right. However, the result must be reduced to an irreducible fraction at each step (since the formula assumes irreducible fractions as input).

Algorithm

1. Initialize the result as \(\frac{A}{B} = \frac{P_1}{Q_1}\) (the input is already irreducible, so it can be used directly).
2. For \(i = 2, 3, \ldots, N\), repeat the following:
   • New numerator: \(A' = \mathrm{lcm}(A, P_i)\)
   • New denominator: \(B' = \gcd(B, Q_i)\)
   • Reduce by \(g = \gcd(A', B')\) to get \(A = A'/g\), \(B = B'/g\).
3. Output the final \(A\) and \(B\).

Here, \(\mathrm{lcm}(a, b) = \frac{a}{\gcd(a,b)} \times b\) is used for computation (dividing first to prevent overflow).

Complexity

• Time complexity: \(O(N \log V)\) (\(V\) is the upper bound of the values; GCD computation at each step is \(O(\log V)\))
• Space complexity: \(O(1)\) (only a constant number of variables aside from input)

Implementation Notes

• Maintaining irreducible fractions: Since the formula assumes both inputs are irreducible fractions, we need to reduce by \(\gcd\) after each LCM computation to keep the result irreducible.

• Overflow prevention: When computing lcm(A, P), the product \(A \times P\) can become very large, so we compute in the order a // gcd(a, b) * b. In Python, overflow does not occur due to arbitrary-precision integers, but care is needed in languages like C++.

• Fast input: Since \(N\) can be up to \(2 \times 10^5\), we speed up input by reading all at once with sys.stdin.buffer.read().

  Source Code

import sys
from math import gcd

def lcm(a, b):
    return a // gcd(a, b) * b

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    # T_i = P_i / Q_i
    # LCM of rationals: lcm(P1/Q1, P2/Q2) = lcm(P1,P2) / gcd(Q1,Q2)
    
    num = 1  # numerator of result (LCM of all P_i)
    den = 1  # denominator of result (GCD of all Q_i) -- wait, not exactly
    
    # More carefully:
    # LCM(a/b, c/d) = LCM(a,c) / GCD(b,d)
    # But we need to keep it in reduced form as we go to avoid issues.
    
    # Actually, let's think about it differently.
    # Result = A/B in reduced form.
    # We accumulate: start with A=P1, B=Q1 (reduced).
    # Then LCM(A/B, P_i/Q_i) = LCM(A, P_i) / GCD(B, Q_i)... 
    # Wait, this formula works for any two positive rationals, not just reduced ones?
    
    # The formula: For positive rationals r1 = a/b, r2 = c/d (in lowest terms),
    # LCM(r1, r2) = LCM(a,c) / GCD(b,d)
    # This is a known result. Let me verify:
    # LCM(1/2, 1/3) = LCM(1,1)/GCD(2,3) = 1/1 = 1. Check: 1/(1/2)=2 ✓, 1/(1/3)=3 ✓. Good.
    # LCM(2/3, 4/5) = LCM(2,4)/GCD(3,5) = 4/1 = 4. Check: 4/(2/3)=6 ✓, 4/(4/5)=5 ✓. Good.
    
    # But we need both fractions to be in lowest terms for this formula to work.
    # So after each step, we should reduce.
    
    A = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    # A/B is already in lowest terms per problem statement
    
    for i in range(1, N):
        P = int(input_data[idx]); idx += 1
        Q = int(input_data[idx]); idx += 1
        
        # LCM(A/B, P/Q) = LCM(A,P) / GCD(B,Q), then reduce
        new_A = lcm(A, P)
        new_B = gcd(B, Q)
        
        g = gcd(new_A, new_B)
        A = new_A // g
        B = new_B // g
    
    print(A, B)

main()

---

This editorial was generated by claude4.6opus-thinking.