Learning C++ Programming from Scratch, Day 412: Least Common Multiple of Two Numbers M and N; Question Bank Answers; Second Method

1087 – Least Common Multiple of Two Numbers M and N

1. Problem Understanding Phase (Fully Understand the Requirements)

The problem we need to solve is: to calculate the least common multiple of two positive integers M and N. The least common multiple is the smallest positive integer that can be divided by both M and N.

For example:

The least common multiple of M=4 and N=6 is 12
The least common multiple of M=5 and N=7 is 35
The least common multiple of M=12 and N=18 is 36

2. Core Algorithm Idea

The program uses the Euclidean algorithm to calculate the least common multiple, which consists of two steps:

First, calculate the greatest common divisor (GCD)
Then use the formula: Least Common Multiple = (M × N) / GCD

3. Detailed Execution Process (Taking M=12, N=18 as an Example)

Calculate GCD(12,18):

12 % 18 = 12 → GCD(18,12)
18 % 12 = 6 → GCD(12,6)
12 % 6 = 0 → Return 6

Calculate LCM:

(12 × 18) / 6 = 216 / 6 = 36

Reference Code

#include <bits/stdc++.h> // Include all standard library headers
using namespace std;    // Use standard namespace
/* * Calculate the greatest common divisor (GCD) of two numbers * Using the Euclidean algorithm * Parameters: m and n are the two numbers to be calculated * Return value: greatest common divisor */
long long gcd(long long m, long long n) {
    if (m % n == 0) {  // If m is divisible by n
        return n;      // n is the greatest common divisor
    }
    else {
        return gcd(n, m % n); // Otherwise, recursively calculate GCD of n and m%n
    }
}
/* * Calculate the least common multiple (LCM) of two numbers * Using the formula: LCM = (m / GCD) * n * Parameters: m and n are the two numbers to be calculated, x is their GCD * Return value: least common multiple */
long long gbs(long long m, long long n, long long x) {
    return m / x * n; // Divide first to avoid overflow
}
int main() {
    long long m, n; // Define two long long variables to store input
    cin >> m >> n;  // Read two numbers from user input
    // Calculate and output the least common multiple
    cout << gbs(m, n, gcd(m, n)) << endl;
    return 0; // Program ends normally
}

Super Detailed Program Documentation (For Beginners)

1. Program Function Description

This program calculates: the least common multiple of any two given positive integers M and N. The least common multiple is the smallest positive integer that can be divided by both M and N.

2. Core Algorithm Analysis

Calculation Steps:

Calculate the greatest common divisor (GCD):

Use the Euclidean algorithm
Recursively calculate until the remainder is 0

Calculate the least common multiple (LCM):

Use the formula: LCM = (M × N) / GCD
Optimization: divide first to avoid large number overflow

3. Variable Function Description

m and n: store the two numbers input by the user
gcd() function: calculates the greatest common divisor
gbs() function: calculates the least common multiple

4. Execution Process Example (M=12, N=18)

Calculate GCD:

12%18=12 → gcd(18,12)
18%12=6 → gcd(12,6)
12%6=0 → Return 6

gcd(12,18)

Calculate LCM:

(12/6)*18=2 * 18=36

gbs(12,18,6)

5. Recursive Call Diagram

gcd(12,18)
│
├── 12%18=12 → gcd(18,12)
│   │
│   ├── 18%12=6 → gcd(12,6)
│   │   │
│   │   ├── 12%6=0 → Return 6
│   │   │
│   │   └── Return 6
│   │
│   └── Return 6
│
└── Return 6

6. Important Notes

Data Type:

Use long long to prevent overflow with large numbers

Calculation Order:

Divide first to avoid overflow in intermediate results

Recursive Termination:

Terminate recursion when the remainder is 0

7. Reference Test Cases

Input M	Input N	GCD	LCM
12	18	6	36
5	7	1	35
24	16	8	48
17	23	1	391

This explanation is entirely based on the original code, providing the most detailed execution process analysis to help beginners understand the algorithm principles and the specific behavior of the program.