sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/gcd_of_gaussian_integers" #include <bits/stdc++.h> #include "../../math/gaussian_integer.hpp" using namespace std; using G = GaussianInteger<long long>; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { long long a1, b1, a2, b2; cin >> a1 >> b1 >> a2 >> b2; G x(a1, b1), y(a2, b2); auto g = G::gcd(x, y); cout << g.x << " " << g.y << "\n"; } }
#line 1 "test/yosupo/gcd_of_gaussian_integers.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/gcd_of_gaussian_integers" #include <bits/stdc++.h> #line 4 "math/gaussian_integer.hpp" /** * @brief Gaussian Integer */ template <typename T> struct GaussianInteger { using G = GaussianInteger<T>; T x, y; GaussianInteger() = default; explicit GaussianInteger(T x) : x(x), y(0) {} constexpr GaussianInteger(T x, T y) : x(x), y(y) {} constexpr G& operator+=(const G& r) noexcept { x += r.x, y += r.y; return *this; } constexpr G& operator-=(const G& r) noexcept { x -= r.x, y -= r.y; return *this; } constexpr G& operator*=(const G& r) noexcept { T nx = x * r.x - y * r.y; T ny = x * r.y + y * r.x; x = nx, y = ny; return *this; } constexpr G operator-() const noexcept { return G(-x, -y); } constexpr G operator+(const G& r) const noexcept { return G(*this) += r; } constexpr G operator-(const G& r) const noexcept { return G(*this) -= r; } constexpr G operator*(const G& r) const noexcept { return G(*this) *= r; } constexpr bool operator==(const G& r) const noexcept { return x == r.x && y == r.y; } constexpr bool operator!=(const G& r) const noexcept { return x != r.x || y != r.y; } constexpr G conj() const { return G(x, -y); } constexpr T norm() const { return x * x + y * y; } static constexpr std::pair<G, G> divmod(const G& a, const G& b) { assert(b.norm() > 0); if (a.norm() < b.norm()) return {G(0), G(a)}; G num = a * b.conj(); T den = b.norm(); auto [qx, rx] = divmod(num.x, den); if (rx > den / 2) ++qx; auto [qy, ry] = divmod(num.y, den); if (ry > den / 2) ++qy; G q(qx, qy); return {q, a - q * b}; } static constexpr G gcd(G a, G b) { while (b.norm() > 0) { auto [q, r] = divmod(a, b); a = b; b = r; } return a; } friend std::ostream& operator<<(std::ostream& os, const G& r) { return os << r.x << "+" << r.y << "i"; } private: static constexpr std::pair<T, T> divmod(T a, T b) { assert(b > 0); T q = a / b; if (a == b * q) return {q, 0}; if (a < 0) --q; return {q, a - b * q}; } }; #line 6 "test/yosupo/gcd_of_gaussian_integers.test.cpp" using namespace std; using G = GaussianInteger<long long>; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { long long a1, b1, a2, b2; cin >> a1 >> b1 >> a2 >> b2; G x(a1, b1), y(a2, b2); auto g = G::gcd(x, y); cout << g.x << " " << g.y << "\n"; } }