cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2026 · MediumLeast Common Multiple of Fractions

Least Common Multiple of Fractions

Национална олимпиада - Национален кръг 2026

Submission name: frac.cpp

Solve in Editor →

Problem summary

Find the smallest positive fraction x/y whose quotient by every supplied fraction is a positive integer. Input fractions are reduced.

Input

n followed by n numerator denominator pairs.

Output

The reduced numerator x and denominator y.

Constraints

1 ≤ n ≤ 20; numerators ≤ 10^6, denominators ≤ 10^7; resulting x,y < 10^9.

Worked example

The worked example illustrates the rule described in the analysis.

Input

2
15 16
7 22

Output

105 2

Solution analysis

  1. Compute L, the least common multiple of all numerators, and G, the greatest common divisor of all denominators. The answer is L/G.
  2. Update the LCM as L/gcd(L,a)×a, dividing before multiplication. Update G by gcd(G,b), starting G at zero.
  3. For 15/16 and 7/22, L=105 and G=2. The resulting 105/2 divided by the inputs gives 56 and 165, both integers. Reduced input fractions imply that no prime can divide both L and G.

Why it works

For each prime p, the exponent of p in a rational multiple must be at least the maximum exponent among the input fractions. Reduced fractions ensure this maximum equals the numerator LCM exponent minus the denominator GCD exponent: if a positive numerator exponent exists, some denominator exponent is zero; otherwise every numerator exponent is zero. Thus L/G has exactly the componentwise minimum required exponents.

Complexity: O(n log V) time for gcd operations and O(1) auxiliary space. Partial numerator LCMs divide the final numerator, so the promised result bound keeps intermediate values safe in long long.

Watch out. Use reduced input fractions and divide before multiplying. The operation is LCM on numerators but GCD on denominators. Do not add the fractions.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: For each prime p, the exponent of p in a rational multiple must be at least the maximum
// exponent among the input fractions. Reduced fractions ensure this maximum equals the numerator LCM
// exponent minus the denominator GCD exponent: if a positive numerator exponent exists, some
// denominator exponent is zero; otherwise every numerator exponent is zero.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    long long numerator=1,denominator=0;
    for(int i=0;i<n;++i){
        long long a,b;
        cin>>a>>b;
        numerator=numerator/gcd(numerator,a)*a;
        denominator=gcd(denominator,b);
    }
    cout<<numerator<<' '<<denominator<<'\n';
}

Source: Arena Olimpiici ↗