Enumerate mod inv
(Mylib/Number/Mod/enumerate_mod_inv.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

• enumerate_mod_inv(n, p)
  • p is prime
  • Time complexity $O(n)$

Requirements

Notes

Problems

References

Code

#pragma once
#include <cstdint>
#include <vector>

namespace haar_lib {
  std::vector<int64_t> enumerate_mod_inv(int n, int64_t p) {
    std::vector<int64_t> ret(n + 1);

    ret[1] = 1;

    for (int i = 2; i <= n; ++i) {
      ret[i] = (p / i) * (p - ret[p % i]) % p;
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/Mod/enumerate_mod_inv.cpp"
#include <cstdint>
#include <vector>

namespace haar_lib {
  std::vector<int64_t> enumerate_mod_inv(int n, int64_t p) {
    std::vector<int64_t> ret(n + 1);

    ret[1] = 1;

    for (int i = 2; i <= n; ++i) {
      ret[i] = (p / i) * (p - ret[p % i]) % p;
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page