# Exponent: C++17 参考实现

本目录配套题解：`/algo/training/icpc-2026-online-ii-exponent/`。

`main.cpp` 是本次独立编写的参考实现。输入为 T 行模数，T<=1000、1<=n<=10^9；输出模 n 乘法阶之和，不可逆元素贡献 0，n=1 输出 1。不需要账户或外部库，未向 OJ 提交，不宣称 AC。

## 编译与运行

在自行准备的本地工作目录运行，编译输出和编译器临时目录都应留在工作区。以下为 shell 示例；Windows PowerShell 可用 `Get-Content sample-1.in | ./exponent.exe` 输入数据。

```sh
g++ -std=c++17 -O2 -Wall -Wextra -Wconversion -pedantic-errors main.cpp -o exponent
./exponent < sample-1.in
./exponent < sample-2.in
```

输出应分别与 `sample-1.out`、`sample-2.out` 相同。示例命令假定已把 TMP/TEMP/TMPDIR 指向允许使用的本地工作目录；配套验证脚本会自动将子进程临时目录放到验证目录的 `cache/` 下。

## 实现要点

- 先按模数素数幂生成循环长度：奇 p^e 对应 p^(e-1)(p-1)；2 对应平凡群；4 对应 2；e>=3 的 2^e 对应 2 和 2^(e-2)。
- 循环长度再按素数分组。对 q 分量，F(k)=q^(sum min(k,b_i))，贡献是 1+sum q^k(F(k)-F(k-1))。
- `active` 记录 b_i>=k 的因子个数，用整数连乘递推 F，禁止浮点幂。
- 只在不同素数的群分量之间乘贡献。答案不是模数 n 的普通积性函数，例如 A(15)=23，而 A(3)A(5)=33。
- 计数阶段 O(log n)，试除阶段 O((omega(n)+1)pi(sqrt(n)))；std::map 建表另有 O(log n log log(n+2)) 上界。素数筛一次 O(31623 log log 31623)。
- 答案、单项贡献、局部和及前缀乘积均不超过 phi(n)^2<=10^18，使用 std::int64_t，乘法操作数即为 64 位，无需 __int128。

## 验证与来源

本目录的 [verification.md](verification.md) 记录测试范围与代码版本。小规模用直接模乘暴力差分，大规模用 Python 任意精度的约数 Möbius 反演核对，不复用主算法的逐素数加权递推。完整脚本、数据和执行记录在内部验证证据中保留。

题目与样例来源：[QOJ 20240](https://qoj.ac/problem/20240)。公式和复杂度独立核对来源：[赛方中文题解第 3-4 页](https://codeforces.com/gym/106701/attachments/download/39422/sol.pdf#page=3)。群结构来源：[Keith Conrad 作者讲义](https://kconrad.math.uconn.edu/blurbs/gradnumthy/primepowerunitsandGLnQ.pdf)。实现未复制第三方代码或竞赛模板；引用的数学结论不等于引用其实现。