模板 - 光速幂

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

光速幂是一种针对固定底数和模数的高速求幂算法，其基本思路和 BSGS 相同

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

基本思路和 BSGS 相同，就是分成两块 \(y=a\lfloor\sqrt p\rfloor+b\) 然后就有

\[ x^y=\left(x^{\lfloor\sqrt p\rfloor}\right)^a+x^b \]

当然也可以分成长度为 256 的四个块来卡 cache

Show code

rpow.hppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename Tp = int64_t>
class rpow final {
private:
  uint32_t mod;
  Tp base;
  std::array<Tp, 65536> block1, block2;

public:
  rpow(const Tp &_base, const uint32_t &_mod): base(_base), mod(_mod) {
    block1[0] = block2[0] = 1;
    for (uint32_t i = 1; i < 65536; i++) block1[i] = block1[i - 1] * base % mod;
    Tp _(block1.back() * base % mod);
    for (uint32_t i = 1; i < 65536; i++) block2[i] = block2[i - 1] * _ % mod;
  }

  Tp &&get_base() { return std::move(base); }
  uint32_t &&get_mod() { return std::move(mod); }

  Tp operator()(std::make_unsigned_t<Tp> &&exponent) {
    return block1[exponent & 65535] * block2[exponent >> 16] % mod;
  }
};