mod/mod_inv_u64.hpp

• View this file on GitHub
• Last update: 2026-02-03 22:59:09+09:00
• Include: #include "mod/mod_inv_u64.hpp"

Required by

• mod/mod_log_u64.hpp

Code

u64 mod_inv_u64(u64 a) {
  assert(a & 1);
  u64 x = 1;
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  assert(a * x == 1);
  return x;
}

#line 1 "mod/mod_inv_u64.hpp"
u64 mod_inv_u64(u64 a) {
  assert(a & 1);
  u64 x = 1;
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  x = x * (2ULL - a * x);
  assert(a * x == 1);
  return x;
}

Back to top page