模板 - Gauss 整数

发表于 更新于 分类于 ， 本文字数： 128 阅读时长 ≈ 1 分钟

基于 C++14, 实现了 Gauss 整数的四则运算

定义 Gauss 整数: \(\mathbb{Z}[\sqrt{-k}]:=\{a+b\sqrt{-k}|a,b\in\Bbb{Z}\}\), \(k>0\)

  • 仅在 GCC 下测试过
  • 没有防溢出措施，建议使用时搭配 modint

https://cplib.tifa-233.com/src/code/math/gint.hpp 存放了笔者对该算法 / 数据结构的最新实现，建议前往此处查看相关代码

Show code

GaussInt.hppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Z[sqrt(p)], p < 0
//! NO overflow protect
template <class Tp, int p = -1>
class GaussInt {
  static_assert(p < 0, "p should be negative");

  using self = GaussInt<Tp, p>;

protected:
  Tp r_, i_;

public:
  constexpr GaussInt(Tp real = Tp{}, Tp imag = Tp{}): r_(real), i_(imag) {}

  constexpr friend std::istream &operator>>(std::istream &is, self &x) {
    return is >> x.r_ >> x.i_;
  }
  constexpr friend std::ostream &operator<<(std::ostream &os, const self &x) {
    return os << x.r_ << " " << x.i_;
  }

  constexpr Tp norm() const { return r_ * r_ + i_ * i_ * -p; }
  constexpr self conj() const { return self(r_, -i_); }

  constexpr self &operator*=(const Tp &k) {
    r_ *= k;
    i_ *= k;
    return *this;
  }
  constexpr friend self operator*(self lhs, const Tp &k) { return lhs *= k; }
  constexpr friend self operator*(const Tp &k, self lhs) { return lhs *= k; }
  constexpr self &operator/=(const Tp &k) {
    r_ /= k;
    i_ /= k;
    return *this;
  }
  constexpr friend self operator/(self lhs, const Tp &k) { return lhs /= k; }

  constexpr self &operator+=(const self &rhs) {
    r_ += rhs.r_;
    i_ += rhs.i_;
    return *this;
  }
  constexpr friend self operator+(self lhs, const self &rhs) {
    return lhs += rhs;
  }
  constexpr self &operator-=(const self &rhs) {
    r_ -= rhs.r_;
    i_ -= rhs.i_;
    return *this;
  }
  constexpr friend self operator-(self lhs, const self &rhs) {
    return lhs -= rhs;
  }

  constexpr self &operator*=(const self &rhs) {
    Tp a = r_, b = i_;
    r_ = a * rhs.r_ + b * rhs.i_ * p;
    i_ = b * rhs.r_ + a * rhs.i_;
    return *this;
  }
  constexpr friend self operator*(self lhs, const self &rhs) {
    return lhs *= rhs;
  }
  constexpr self &operator/=(const self &rhs) {
    return (*this *= rhs.conj()) /= rhs.norm();
  }
  constexpr friend self operator/(self lhs, const self &rhs) {
    return lhs /= rhs;
  }
};