number/gcd.hpp

• View this file on GitHub
• Last update: 2019-06-04 14:45:23+09:00
• Include: #include "number/gcd.hpp"

Required by

• monoids/gcd.hpp

Verified with

• data_structure/sparse_table.yukicoder-1036.test.cpp

Code

#pragma once
#include <algorithm>

/**
 * @note if arguments are negative, the result may be negative
 */
template <typename T>
T gcd(T a, T b) {
    while (a) {
        b %= a;
        std::swap(a, b);
    }
    return b;
}

template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

#line 2 "number/gcd.hpp"
#include <algorithm>

/**
 * @note if arguments are negative, the result may be negative
 */
template <typename T>
T gcd(T a, T b) {
    while (a) {
        b %= a;
        std::swap(a, b);
    }
    return b;
}

template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

Back to top page