Skip to main content

Arithmetic

Operators​

namespace Math {
  inline int32_t madd(int32_t a, int32_t b, int32_t m) { a += b; return (a >= m) ? (a - m) : a; }
  inline int32_t msub(int32_t a, int32_t b, int32_t m) { a -= b; return (a >= 0) ? a : (a + m); }
  inline int32_t mmul(int32_t a, int32_t b, int32_t m) { return static_cast<int64_t>(a) * b % m; }

  inline void maddi(int32_t &a, int32_t b, int32_t m) { a += b; if (a >= m) a -= m; }
  inline void msubi(int32_t &a, int32_t b, int32_t m) { a -= b; if (a <  0) a += m; }
  inline void mmuli(int32_t &a, int32_t b, int32_t m) { a = static_cast<int64_t>(a) * b % m; }
}

Power​

namespace Math {
  int64_t pow(int64_t a, int64_t b) {
    int64_t r = 1;
    for (; b > 0; b >>= 1) if (b & 1) r *= a; a *= a;
    return r;
  }
}

namespace Math {
  int32_t mpow(int32_t a, int64_t b, int32_t m) {
    int32_t r = 1;
    for (b %= (m - 1); b > 0; b >>= 1) if (b & 1) mmuli(r, a, m); mmuli(a, a, m);
    return r;
  }
}

Inverse​

Recursive​

REFERENCES
namespace Math {
    int32_t minv(int32_t a, int32_t m) {
        if (a <= 1) return 1;
        return static_cast<int32_t>(m - static_cast<int64_t>(minv(m % a, a)) * m / a);
    }
}

Iterative​

namespace Math {
  int32_t minv_iterative(int32_t a, int32_t m = MOD) {
    int32_t g = m, r = a, x = 0, y = 1;
    while (r != 0) {
      int32_t q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
}

Linear for range ​

int main {
  int inv[n], mod = 1000000007;
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;
  }
}