@[www2003](/user/87651) 不要用unordered_map, 非常慢，用手动hash, 由于sqrt(phi)最大值也就是在40000左右，所以hash的模数可以去100007. 就是hash = num % 100007。实践证明，碰撞非常少，而认为近似O(1).
```cpp
struct HashNode {
uint32_t num;
uint32_t exponent;
uint32_t next;
};
const int32_t kModular = 100007;
uint32_t head[kModular];
HashNode record[kModular];
int id;
pair<bool, uint32_t> HashFind(uint32_t num)
{
uint32_t idx;
uint32_t hash = num % kModular;
idx = head[hash];
while (idx != 0) {
if (record[idx].num == num) {
return make_pair(true, record[idx].exponent);
}
idx = record[idx].next;
}
return make_pair(false, 0);
}
void HashInsert(uint32_t num, uint32_t exponent)
{
uint32_t hash = num % kModular;
++id;
record[id].num = num;
record[id].exponent = exponent;
record[id].next = head[hash];
head[hash] = id;
}
```
by damocris @ 2021-12-06 16:47:03
@[damocris](/user/119884) 谢谢
by www2003 @ 2021-12-08 22:00:26