取模运算优化超级算法
【摘要】
#ifndef LOCAL#define NDEBUG#endif#include <algorithm>#include <cassert>#include <cstring>#include <functional>#include <initializer_list>#i...
#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
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)