取模运算优化超级算法

      #ifndef LOCAL
      #define NDEBUG
      #endif
      #include <algorithm>
      #include <cassert>
      #include <cstring>
      #include <functional>
      #include <initializer_list>
      #include <iostream>
      #include <memory>
      #include <queue>
      #include <random>
      #include <vector>
      template <std::uint32_t P> struct ModInt32 {
      public:
       using i32 = std::int32_t;
       using u32 = std::uint32_t;
       using i64 = std::int64_t;
       using u64 = std::uint64_t;
       using m32 = ModInt32;
      private:
        u32 v;
       static constexpr u32 get_r() {
          u32 iv = P;
         for (u32 i = 0; i != 4; ++i) iv *= 2U - P * iv;
         return -iv;
        }
       static constexpr u32 r = get_r(), r2 = -u64(P) % P;
       static_assert((P & 1) == 1);
       static_assert(-r * P == 1);
       static_assert(P < (1 << 30));
       static constexpr u32 pow_mod(u32 x, u64 y) {
          u32 res = 1;
         for (; y != 0; y >>= 1, x = u64(x) * x % P)
           if (y & 1) res = u64(res) * x % P;
         return res;
        }
       static constexpr u32 reduce(u64 x) { return x + u64(u32(x) * r) * P >> 32; }
       static constexpr u32 norm(u32 x) { return x - (P & -(x >= P)); }
      public:
       static constexpr u32 get_pr() {
          u32 tmp[32] = {}, cnt = 0;
         const u64 phi = P - 1;
          u64 m = phi;
         for (u64 i = 2; i * i <= m; ++i)
           if (m % i == 0) {
              tmp[cnt++] = i;
             while (m % i == 0) m /= i;
            }
         if (m != 1) tmp[cnt++] = m;
         for (u64 res = 2; res != P; ++res) {
           bool flag = true;
           for (u32 i = 0; i != cnt && flag; ++i) flag &= pow_mod(res, phi / tmp[i]) != 1;
           if (flag) return res;
          }
         return 0;
        }
       ModInt32() = default;
        ~ModInt32() = default;
       constexpr ModInt32(u32 v) : v(reduce(u64(v) * r2)) {}
       constexpr ModInt32(const m32 &rhs) : v(rhs.v) {}
       constexpr u32 get() const { return norm(reduce(v)); }
       explicit constexpr operator u32() const { return get(); }
       explicit constexpr operator i32() const { return i32(get()); }
       constexpr m32 &operator=(const m32 &rhs) { return v = rhs.v, *this; }
       constexpr m32 operator-() const {
          m32 res;
         return res.v = (P << 1 & -(v != 0)) - v, res;
        }
       constexpr m32 inv() const { return pow(-1); }
       constexpr m32 &operator+=(const m32 &rhs) {
         return v += rhs.v - (P << 1), v += P << 1 & -(v >> 31), *this;
        }
       constexpr m32 &operator-=(const m32 &rhs) { return v -= rhs.v, v += P << 1 & -(v >> 31), *this; }
       constexpr m32 &operator*=(const m32 &rhs) { return v = reduce(u64(v) * rhs.v), *this; }
       constexpr m32 &operator/=(const m32 &rhs) { return this->operator*=(rhs.inv()); }
       friend m32 operator+(const m32 &lhs, const m32 &rhs) { return m32(lhs) += rhs; }
       friend m32 operator-(const m32 &lhs, const m32 &rhs) { return m32(lhs) -= rhs; }
       friend m32 operator*(const m32 &lhs, const m32 &rhs) { return m32(lhs) *= rhs; }
       friend m32 operator/(const m32 &lhs, const m32 &rhs) { return m32(lhs) /= rhs; }
       friend bool operator==(const m32 &lhs, const m32 &rhs) { return norm(lhs.v) == norm(rhs.v); }
       friend bool operator!=(const m32 &lhs, const m32 &rhs) { return norm(lhs.v) != norm(rhs.v); }
       friend std::istream &operator>>(std::istream &is, m32 &rhs) {
         return is >> rhs.v, rhs.v = reduce(u64(rhs.v) * r2), is;
        }
       friend std::ostream &operator<<(std::ostream &os, const m32 &rhs) { return os << rhs.get(); }
       constexpr m32 pow(i64 y) const {
         if ((y %= P - 1) < 0) y += P - 1; // phi(P) = P - 1, assume P is a prime number
         m32 res(1), x(*this);
         for (; y != 0; y >>= 1, x *= x)
           if (y & 1) res *= x;
         return res;
        }
      };
      int main() {
      #ifdef LOCAL
        std::freopen("..\\in", "r", stdin), std::freopen("..\\out", "w", stdout);
      #endif
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
       // 使用方法： ModInt32<7> a(3);
       ModInt32<7> a(11);
        std::cout << a;
       return 0;
      }
  
 

  
 
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/126829172