取模运算优化超级算法

  

   

    

     

    
    

     

      #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