This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tkmst201/Library
#define PROBLEM "https://yukicoder.me/problems/no/415" #include "Mathematics/euclid.hpp" #include <cstdio> #include <cassert> int main() { int N, D; scanf("%d %d", &N, &D); long long lcm = tk::lcm<long long>(N, D); assert(lcm / D - 1 == N / tk::gcd(N, D) - 1); printf("%d\n", N / tk::gcd(N, D) - 1); }
#line 1 "Test/euclid.gcd.lcm.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/415" #line 1 "Mathematics/euclid.hpp" #include <cassert> #include <utility> #include <tuple> #include <type_traits> #include <cmath> /** * @brief https://tkmst201.github.io/Library/Mathematics/euclid.hpp */ namespace tk { template<typename T> constexpr T gcd(T a, T b) noexcept { static_assert(std::is_integral<T>::value); assert(a >= 0); assert(b >= 0); while (b != 0) { const T t = a % b; a = b; b = t; } return a; } template<typename T> constexpr T lcm(T a, T b) noexcept { static_assert(std::is_integral<T>::value); assert(a >= 0); assert(b >= 0); if (a == 0 || b == 0) return 0; return a / gcd(a, b) * b; } template<typename T> constexpr std::tuple<T, T, T> ext_gcd(T a, T b) noexcept { static_assert(std::is_integral<T>::value); static_assert(std::is_signed<T>::value); assert(a != 0); assert(b != 0); T a1 = (a > 0) * 2 - 1, a2 = 0, b1 = 0, b2 = (b > 0) * 2 - 1; a = std::abs(a); b = std::abs(b); while (b > 0) { const T q = a / b; T tmp = a - q * b; a = b; b = tmp; tmp = a1 - q * b1; a1 = b1; b1 = tmp; tmp = a2 - q * b2; a2 = b2; b2 = tmp; } return {a, a1, a2}; } } // namespace tk #line 4 "Test/euclid.gcd.lcm.test.cpp" #include <cstdio> #line 7 "Test/euclid.gcd.lcm.test.cpp" int main() { int N, D; scanf("%d %d", &N, &D); long long lcm = tk::lcm<long long>(N, D); assert(lcm / D - 1 == N / tk::gcd(N, D) - 1); printf("%d\n", N / tk::gcd(N, D) - 1); }