verify/aoj-NTL_1_C-least_common_multiple.test.cpp

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_C

Depends on

• Greatest Common Divisor（最大公約数） (algorithm/Math/NumberTheory/greatest_common_divisor.hpp)
• Least Common Multiple（最小公倍数） (algorithm/Math/NumberTheory/least_common_multiple.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_C"

#include <cstdint>
#include <iostream>

#include "../algorithm/Math/NumberTheory/least_common_multiple.hpp"

int main() {
    int n;
    std::cin >> n;

    uint32_t ans = 1;
    for(int i = 0; i < n; ++i) {
        uint32_t a;
        std::cin >> a;

        ans = algorithm::ilcm(ans, a);
    }

    std::cout << ans << std::endl;
}

#line 1 "verify/aoj-NTL_1_C-least_common_multiple.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_C"

#include <cstdint>
#include <iostream>

#line 1 "algorithm/Math/NumberTheory/least_common_multiple.hpp"



/**
 * @brief Least Common Multiple（最小公倍数）
 * @docs docs/Math/NumberTheory/least_common_multiple.md
 */

#line 1 "algorithm/Math/NumberTheory/greatest_common_divisor.hpp"



/**
 * @brief Greatest Common Divisor（最大公約数）
 * @docs docs/Math/NumberTheory/greatest_common_divisor.md
 */

namespace algorithm {

template <typename Type>
constexpr Type igcd(Type a, Type b) { return (b == 0 ? a : igcd(b, a % b)); }

}  // namespace algorithm


#line 10 "algorithm/Math/NumberTheory/least_common_multiple.hpp"

namespace algorithm {

template <typename Type>
constexpr Type ilcm(Type a, Type b) { return a / igcd(a, b) * b; }

}  // namespace algorithm


#line 7 "verify/aoj-NTL_1_C-least_common_multiple.test.cpp"

int main() {
    int n;
    std::cin >> n;

    uint32_t ans = 1;
    for(int i = 0; i < n; ++i) {
        uint32_t a;
        std::cin >> a;

        ans = algorithm::ilcm(ans, a);
    }

    std::cout << ans << std::endl;
}

Back to top page