Least Common Multiple (LCM)

The least common multiple is the smallest positive common multiple of positive integers; conventionally lcm(a,0)=0. It describes when repeating schedules synchronize. Factoring both numbers shows that GCD takes the smaller exponent of each prime while LCM takes the larger. This yields a useful formula, but implementing that formula safely requires division before multiplication and an explicit overflow check.

Prerequisites: Greatest Common Divisor; integer overflow limits.

Build the idea

1. 1. Relate prime powers

   If a contains p to exponent α and b to exponent β, their GCD contains p^min(α,β) and LCM p^max(α,β). Since min+max=α+β, multiplying GCD and LCM gives a·b. Rearranging produces the formula below for positive inputs. Zero needs a separate branch because gcd(0,0)=0 cannot be a divisor in that expression.

   $$\mathrm{lcm}(a,b)=\frac{a}{\gcd (a,b)}·b$$

2. 2. Divide before multiplying

   For 12 and 18, GCD is 6, so LCM=(12/6)·18=36. Computing 12·18 first is harmless here but can overflow on larger legal inputs even when the final quotient fits. Division first removes the shared factor before multiplication. std::lcm also requires a representable result; it is not an overflow detector.

3. 3. Check a product before evaluating it

   With positive reduced=a/g and x, reduced*x fits long long exactly when reduced≤LLONG_MAX/x. Use numeric_limits<long long>::max() and this division comparison; do not compute the product and then inspect a wrapped or undefined result. All inputs here are nonnegative, so no signed-minimum absolute-value conversion is needed.

4. 4. Combine multiple values

   Maintain the LCM of the processed prefix and combine the next number. The identity element for positive LCM is 1. For [6,10,15], values progress 6,30,30. A later zero makes the full LCM zero even if an earlier positive-prefix LCM would overflow. The program reads the whole list and checks for zero first, so it does not report overflow prematurely in that case.

5. 5. Interpret limitations honestly

   If no zero exists and a combination exceeds the type, print OVERFLOW instead of a false integer. Wider exact arithmetic or a problem-specific cap may be needed in another task. LCM can grow very quickly for mostly coprime values; a small input count does not guarantee a small result. Bounds on individual values alone do not bound their combined LCM to the same scale.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Interpret limitations honestly If no zero exists and a combination exceeds the type,
// print OVERFLOW instead of a false integer.
#include<iostream>
#include<vector>
#include<numeric>
#include<limits>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>values(n);
    bool zero=false;
    for(auto&x:values){
        std::cin>>x;
        if(x==0){
            zero=true;
        }
    }
    if(zero){
        std::cout<<0<<'\n';
        return 0;
    }
    long long answer=1;
    for(long long x:values){
        long long reduced=answer/std::gcd(answer,x);
        if(reduced>std::numeric_limits<long long>::max()/x){
            std::cout<<"OVERFLOW\n";
            return 0;
        }
        answer=reduced*x;
    }
    std::cout<<answer<<'\n';
}

Complexity analysis

O(n log C) machine-integer remainder work is a safe bound, C being the largest represented intermediate/input scale up to long-long limits. O(n) storage allows the initial zero check before combining. Each product check is O(1). An overflow report is intentional rather than exact computation beyond the type.

Example input and output

Read n (1..200000), then n integers in 0..10^12. Print their LCM if representable as long long, 0 if any input is zero, otherwise OVERFLOW.

Input

3
6 10 15

Output

30

lcm(6,10)=30 and 15 already divides 30, so the third combination stays 30.

Practical applications

Use for synchronizing periods and finding common multiple constraints. Use GCD when looking for shared factors or a greatest step size. In counting problems it may be sufficient to cap an LCM above a query range rather than compute its huge exact value; justify such a cap from the requested answer.

Check your understanding

Why compute a/gcd(a,b) before multiplying by b?

Put it into practice

Test a pair whose product overflows but LCM fits, and a list ending in zero.