Lost大佬有实力，我改进了您的代码
2026-02-06 16:29:18
发布于：湖南
42阅读
0回复
0点赞
感谢Lost大佬
Lost大佬的【科技】强制在线 O(1) 逆元
改进版（减少时间复杂度和空间复杂度）：
#include <iostream>
#include <vector>
#include <cstdint>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define inline __attribute__((always_inline)) inline
#define FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr); cin.tie(0)
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
namespace Loyalty {
vector<uint16_t> farey_num;
vector<uint16_t> farey_den;
vector<uint32_t> pre_sum;
vector<uint32_t> small_inv;
uint32_t mod;
uint32_t n, m;
uint32_t threshold;
uint32_t farey_size;
inline uint32_t integer_cbrt(uint64_t x) noexcept {
if (unlikely(x == 0)) return 0;
uint32_t l = 1, r = 1000001, ans = 1;
while (l <= r) {
const uint32_t mid = (l + r) >> 1;
const uint64_t mid_cu = (uint64_t)mid * mid * mid;
if (mid_cu <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
inline uint32_t binary_gcd(uint32_t a, uint32_t b) noexcept {
if (unlikely(a == 0)) return b;
if (unlikely(b == 0)) return a;
int shift = __builtin_ctz(a | b);
a >>= __builtin_ctz(a);
do {
b >>= __builtin_ctz(b);
if (a > b) swap(a, b);
b -= a;
} while (b != 0);
return a << shift;
}
void nr_init(uint32_t p) noexcept {
mod = p;
n = integer_cbrt(p);
m = (uint64_t)n * n;
threshold = p / n;
pre_sum.assign(m + 1, 0);
for (uint32_t i = 1; i < n; ++i) {
for (uint32_t j = 0; j <= i; ++j) {
if (unlikely(binary_gcd(j, i) != 1)) continue;
const uint64_t val_64 = (uint64_t)j * m / i;
const uint32_t val = (uint32_t)val_64;
if (unlikely(val > m || pre_sum[val])) continue;
pre_sum[val] = 1;
}
}
for (uint32_t i = 1; i <= m; ++i) {
pre_sum[i] += pre_sum[i - 1];
}
farey_num.clear();
farey_den.clear();
farey_num.reserve(pre_sum[m]);
farey_den.reserve(pre_sum[m]);
for (uint32_t i = 1; i < n; ++i) {
for (uint32_t j = 0; j <= i; ++j) {
if (unlikely(binary_gcd(j, i) != 1)) continue;
const uint64_t val_64 = (uint64_t)j * m / i;
const uint32_t val = (uint32_t)val_64;
if (unlikely(val > m)) continue;
farey_num.push_back((uint16_t)j);
farey_den.push_back((uint16_t)i);
}
}
farey_size = farey_num.size();
const uint32_t inv_max = p / n;
small_inv.assign(inv_max + 1, 1);
for (uint32_t i = 2; i <= inv_max; ++i) {
small_inv[i] = (uint32_t)((uint64_t)small_inv[p % i] * (p - p / i) % p);
}
}
inline int32_t try_compute_inv(uint32_t a, uint32_t pos) noexcept {
const uint32_t x = farey_num[pos];
const uint32_t y = farey_den[pos];
const int64_t w = (int64_t)a * y - (int64_t)x * mod;
const uint64_t abs_w = llabs(w);
if (unlikely(abs_w > threshold)) return -1;
uint32_t inv_w;
if (likely(w >= 0)) {
inv_w = small_inv[(uint32_t)abs_w];
} else {
inv_w = mod - small_inv[(uint32_t)abs_w];
}
return (int32_t)((uint64_t)y * inv_w % mod);
}
inline uint32_t bin_gcd_inv(uint32_t a, uint32_t p) noexcept {
a %= p;
uint32_t b = p, u = 1, v = 0, shift = 0;
while (likely(((a | b) & 1) == 0)) {
a >>= 1;
b >>= 1;
shift++;
}
while (a > 0) {
while (likely((a & 1) == 0)) {
a >>= 1;
if (unlikely(u & 1)) u += p;
u >>= 1;
}
while (likely((b & 1) == 0)) {
b >>= 1;
if (unlikely(v & 1)) v += p;
v >>= 1;
}
if (a >= b) {
a -= b;
u -= v;
} else {
b -= a;
v -= u;
}
u %= p;
v %= p;
}
u = (u % p + p) % p;
while (shift--) u = (u << 1) % p;
return u;
}
uint32_t inv(uint32_t a) noexcept {
a %= mod;
if (unlikely(a == 0)) return 0;
if (likely(a == 1)) return 1;
const uint64_t val_64 = (uint64_t)a * m / mod;
const uint32_t val = (uint32_t)val_64;
int32_t res;
if (pre_sum[val] < farey_size) {
res = try_compute_inv(a, pre_sum[val]);
if (likely(res != -1)) return (uint32_t)res;
}
if (pre_sum[val] > 0) {
res = try_compute_inv(a, pre_sum[val] - 1);
if (likely(res != -1)) return (uint32_t)res;
}
return bin_gcd_inv(a, mod);
}
void clear_all() noexcept {
farey_num.clear();
farey_num.shrink_to_fit();
farey_den.clear();
farey_den.shrink_to_fit();
small_inv.clear();
small_inv.shrink_to_fit();
pre_sum.clear();
pre_sum.shrink_to_fit();
}
}
uint32_t p, Q, op, ol;
namespace code {
constexpr uint32_t inv_table[20][20] = {
{0}, {0},
{0, 1},
{0, 1, 2},
{0, 1, 0, 3},
{0, 1, 3, 2, 4},
{0, 1, 0, 0, 0, 5},
{0, 1, 4, 5, 2, 3, 6},
{0, 1, 0, 3, 0, 5, 0, 7},
{0, 1, 0, 6, 0, 0, 0, 3, 0, 2},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 9},
{0, 1, 6, 4, 3, 9, 2, 8, 7, 5, 10, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11},
{0, 1, 7, 9, 10, 8, 11, 2, 5, 3, 4, 6, 12, 0},
{0, 1, 0, 5, 0, 3, 0, 13, 0, 11, 0, 9, 0, 7, 0},
{0, 1, 8, 11, 4, 13, 14, 12, 2, 7, 10, 5, 9, 6, 3, 14},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15},
{0, 1, 9, 6, 13, 7, 3, 5, 15, 2, 12, 14, 8, 4, 10, 11, 16, 0},
{0, 1, 0, 12, 0, 0, 0, 5, 0, 16, 0, 0, 0, 13, 0, 7, 0, 0, 2},
{0, 1, 10, 13, 5, 4, 16, 11, 17, 2, 9, 7, 15, 6, 14, 8, 3, 12, 18, 0}
};
inline void init() noexcept {
if (likely(p >= 20)) {
Loyalty::nr_init(p);
}
}
inline uint32_t solve(uint32_t x) noexcept {
return unlikely(p < 20) ? inv_table[p][x] : Loyalty::inv(x);
}
}
空间复杂度： 最好 / 一般 / 最坏情况 完全一致
核心占用项：
| 容器 | 分配大小 | 空间量级 |
|---|---|---|
pre_sum |
||
farey_num/farey_den |
法里序列长度 | |
small_inv |
时间复杂度：
| 场景 | 单次查询时间复杂度 | 批量查询（次）总复杂度 |
|---|---|---|
| 最好情况 | ||
| 一般情况 | （紧界） | |
| 最坏情况 |
总时间复杂度：
| 场景 | 总时间复杂度 |
|---|---|
| 最好情况 | |
| 一般情况 | |
| 最坏情况 |
全部评论 3
这是你平常练习的码风
#include <bits/stdc++.h> using namespace std; int main(){ int a; cin>>a; if(a<7) { cout<<"Acidic"; }else if(a==7) { cout<<"neutral"; }else { cout<<"alkalinity"; } return 0; }2026-02-07 来自 浙江
0
有帮助，赞一个