ICPC 2026 网络赛第二场 E：Exponent 与单位群的阶之和

这道题的难点不是怎样更快地计算一个数的阶，而是怎样不再逐个计算。我们把求和对象换成有限群的元素，先弄清结构，再一次性统计每种阶的数量。需要补充背景时，可以先读群元素的阶。

题意与边界 #

给定正整数 $n$ ，对 $1\le a\le n$ ，取使 $a^x\equiv1\pmod n$ 成立的最小正整数 $x$ ，作为 $\operatorname{ord}_n(a)$ ；不存在这样的 $x$ 时，贡献为 $0$ 。求这些贡献的总和。共有 $T\le1000$ 组， $n\le10^9$ ，题面时限为 1 秒、内存限制为 512 MB。QOJ 原题

先单独处理 $n=1$ 。这时唯一的 $a=1$ 满足任意正指数的同余条件，最小正指数为 $1$ ，答案就是 $1$ 。不要用“模数太小，直接输出零”的分支处理它。

以下先假定 $n>1$ ，记答案为 $A(n)$ 。

从整数求和到单位群 #

若 $\gcd(a,n)>1$ ，取它们的一个公共素因子 $p$ 。无论正整数 $x$ 是多少， $a^x$ 模 $p$ 都为 $0$ ，不可能同时模 $n$ 等于 $1$ 。因此这些 $a$ 的贡献确实为零。

反之， $\gcd(a,n)=1$ 时， $a$ 属于模 $n$ 的单位群

U(n)=(\mathbb Z/n\mathbb Z)^\times.

这个群有 $\varphi(n)$ 个元素。由拉格朗日定理，每个元素的阶都整除 $\varphi(n)$ ，所以一定存在。区间 $1\ldots n$ 恰好给出了所有剩余类的一组代表，于是

A(n)=\sum_{g\in U(n)}\operatorname{ord}(g).

但这还不是算法。即使每次用快速幂求一个元素的阶，枚举 $\varphi(n)$ 个元素也无法承受 $10^9$ 的规模。我们需要把“枚举元素”换成“计数结构”。

单位群怎样拆开 #

先按模数的素数幂分解 #

设

n=\prod_{i=1}^{s}p_i^{e_i}.

中国剩余定理给出一个保持乘法的双射，因此

U(n)\cong\prod_{i=1}^{s}U(p_i^{e_i}).

这里的群同构不是只告诉我们元素总数相同：一个元素的 $k$ 次幂为单位元，当且仅当它在每个分量上的 $k$ 次幂都为单位元。因此，直积元素的阶是各分量阶的最小公倍数。CRT 的多模数版本及单位的对应见 Keith Conrad 的讲义，第 3 节与定理 4.1。

再把每个单位群写成循环群 #

用 $C_m$ 表示阶为 $m$ 的循环群。各素数幂的规则如下：

模数	单位群结构	需要记录的循环群长度
奇素数幂 $p^e$	$C_{p^{e-1}(p-1)}$	$p^{e-1}(p-1)$
$2$	平凡群	不记录
$4$	$C_2$	$2$
$2^e$ ， $e\ge3$	$C_2\times C_{2^{e-2}}$	$2,2^{e-2}$

奇素数幂的单位群是循环群，这是原根存在定理的结构形式； $2$ 的幂必须另行处理。相应定理见 Conrad，定理 1.1、定理 2.3 与注记 2.4。算法只需要循环群的长度，不需要真的寻找原根。

为什么 $2$ 的幂会出现两个因子？当 $e\ge3$ 时， $-1$ 的阶为 $2$ ， $5$ 的阶为 $2^{e-2}$ 。后者可从

v_2\!\left(5^{2^t}-1\right)=t+2\qquad(t\ge0)

看出：初始 $5-1=4$ ，此后每次平方，新增因子 $5^{2^t}+1$ 恰好含一个 $2$ 。而 $5$ 的所有幂模 $4$ 都为 $1$ ，不可能等于 $-1$ ，故这两个子群交集只有单位元。它们相乘共有 $2\cdot2^{e-2}=\varphi(2^e)$ 个元素，正好填满整个单位群。

至此，我们得到一列非平凡循环群长度 $m_1,\ldots,m_r$ ，使得

U(n)\cong C_{m_1}\times\cdots\times C_{m_r}, \qquad \prod_{j=1}^{r}m_j=\varphi(n).

不能直接把局部答案相乘 #

对于任意两个群，直积元素的阶通常是 $\operatorname{lcm}$ ，不是乘积。因此，不能从 $\gcd(u,v)=1$ 推出 $A(uv)=A(u)A(v)$ 。

例如 $U(3)\cong C_2$ ， $U(5)\cong C_4$ ，但两个群的阶并不互素。实际有

A(3)=3,\quad A(5)=11,\quad A(15)=23\ne33.

模数互素与群的阶互素是两回事。下一步要拆的是循环群长度中的素数，而不只是模数中的素数。

把最小公倍数拆成素数分量 #

对一个循环群长度做素因数分解：

m_j=\prod_q q^{b_{q,j}}.

互素长度的循环群可以按 CRT 拆开，于是

C_{m_j}\cong\prod_{q:b_{q,j}>0}C_{q^{b_{q,j}}}.

把相同素数的因子归在一起，令

G_q=\prod_{j:b_{q,j}>0}C_{q^{b_{q,j}}}, \qquad U(n)\cong\prod_qG_q.

在 $G_q$ 中，每个元素的阶都是 $q$ 的幂；不同 $q$ 对应的元素阶两两互素，所以此时最小公倍数终于等于乘积：

\operatorname{ord}((g_q)_q)=\prod_q\operatorname{ord}(g_q).

各分量的选择组成笛卡尔积，对有限求和使用分配律，就得到

A(n)=\prod_q S_q, \qquad S_q=\sum_{g\in G_q}\operatorname{ord}(g).

注意， $S_q$ 只统计 $G_q$ 内部的选择。其他素数分量的选择数会在最终乘积展开时自然出现，不要再给每个 $S_q$ 额外乘一次 $\varphi(n)$ 。

先数阶整除某个数的元素 #

固定素数 $q$ ，暂时省略下标，写成

G_q=C_{q^{b_1}}\times\cdots\times C_{q^{b_t}}, \qquad B=\max_i b_i.

直接数“阶恰为 $q^k$ ”不够顺手。先定义累积数量

F_q(k)=\#\{g\in G_q:\operatorname{ord}(g)\mid q^k\}.

在循环群 $C_{q^b}=\langle h\rangle$ 中，每个元素唯一写成 $h^x$ ，其中 $0\le x<q^b$ 。它的阶整除 $q^k$ 当且仅当

(h^x)^{q^k}=1 \iff q^b\mid xq^k.

若 $k\ge b$ ，全部 $q^b$ 个指数都可选；若 $k<b$ ，指数 $x$ 必须是 $q^{b-k}$ 的倍数，恰有 $q^k$ 种选择。两种情况合写为 $q^{\min(k,b)}$ 。

直积中每个坐标独立满足这个条件，因此

\boxed{F_q(k)=q^{\sum_{i=1}^{t}\min(k,b_i)}}.

特别地， $F_q(0)=1$ ，对应唯一的单位元。由于元素的阶只能是 $q$ 的幂，阶恰为 $q^k$ 的元素数就是

F_q(k)-F_q(k-1)\qquad(k\ge1).

所以我们真正需要的加权和为

\boxed{S_q=1+\sum_{k=1}^{B}q^k\bigl(F_q(k)-F_q(k-1)\bigr)}.

开头的 $1$ 是单位元的贡献。这里不是只统计有多少种不同的阶，也不是把所有阶取一次最小公倍数。

从公式到高效递推 #

实现里用 freq[q][b] 记录 $C_{q^b}$ 这样的因子出现了几次。处理第 $k$ 层之前，维护

\mathrm{active}=\#\{i:b_i\ge k\}.

从 $k-1$ 到 $k$ ，恰好这些尚未达到上限的坐标各增加一个自由的 $q$ 因子，因此

F_q(k)=F_q(k-1)\,q^{\mathrm{active}}.

代码不使用浮点 pow，而是把上一次计数乘 active 次 $q$ 。完成这一层的贡献后，再减去 freq[q][k]，因为指数恰为 $k$ 的那些因子在下一层不再增长。

乍看这是双重循环，但所有层的乘法次数为

\sum_{k=1}^{B}\#\{i:b_i\ge k\}=\sum_i b_i.

再对不同素数求和，由 $\prod_jm_j=\varphi(n)$ 可得

\sum_q\sum_i b_{q,i}\le\log_2\varphi(n).

因此，获得素因数分解以后，计数部分的整数运算总数只有 $O(\log n)$ 。真正主要的工作是分解 $n$ 和各个 $m_j$ 。

完整流程为：

预处理不超过 $31623$ 的素数，供所有测试复用。
分解 $n$ ，按单位群结构生成循环群长度； $n=1$ 直接输出 $1$ 。
分解每个循环群长度，把素数幂指数计入 freq。
对每个 $q$ 做累积计数差分，算出 $S_q$ ，再把所有 $S_q$ 相乘。

正确性证明 #

第一步，非单位没有满足条件的正指数，单位的题目定义等于它在 $U(n)$ 中的群元素阶。因此原问题就是单位群元素阶之和。

第二步，CRT 和素数幂单位群结构把 $U(n)$ 同构为代码记录的循环群直积；进一步拆分循环长度，得到所有 $G_q$ 。群同构保持元素的阶，没有遗漏或重复元素。

第三步，在 $G_q$ 中，公式 $F_q(k)$ 准确统计了阶整除 $q^k$ 的元素。相邻差分得到阶恰为 $q^k$ 的数量，代码的递推保持 previous = F_q(k-1)、order = q^k 和 active = # {i: b_i >= k}，所以算出的 subtotal 正好是 $S_q$ 。

最后，不同素数分量的阶两两互素，直积元素的阶等于各分量阶的乘积。展开所有 $S_q$ 的乘积，每个单位恰好贡献一次自己的阶，故 answer 等于 $A(n)$ 。 $n=1$ 的单独分支已按原定义处理，算法对全部合法输入成立。

复杂度与整数范围 #

分解成本不能忽略 #

设 $L=31623$ ， $\omega(n)$ 为 $n$ 的不同素因子个数， $\pi(x)$ 为不超过 $x$ 的素数个数。筛法一次需要 $O(L\log\log L)$ 时间和 $O(L)$ 空间。

循环群个数 $r\le\omega(n)+1$ ，每个长度都不超过 $n$ 。包含 $n$ 本身，共分解至多 $r+1$ 个数。试除测试的数量因此有上界

O\bigl((\omega(n)+1)\pi(\sqrt n)\bigr),

反复除掉已找到素因子的总次数另外为 $O(\log n)$ 。这与赛方中文题解第 4 页首行的试除复杂度一致。

本实现使用 std::map 分组，加上建表开销，单组的保守总界为

O\bigl((\omega(n)+1)\pi(\sqrt n)+\log n\log\log(n+2)\bigr).

频次数组与分组记录额外占 $O(\log n)$ 空间。 $n=1$ 单独为 $O(1)$ 。在本题范围内，素数表只有 3401 项， $\omega(n)\le9$ ，因此不需要 Pollard-Rho，也不需要大小为 $n$ 的筛表。不能把“计数阶段 $O(\log n)$ ”误写成整份算法的复杂度。

不只答案，所有乘积都要检查 #

对 $n>1$ ，每个单位的阶不超过 $\varphi(n)$ ，单位共有 $\varphi(n)$ 个，因此

A(n)\le\varphi(n)^2\le10^{18}<2^{63}-1.

再令 $M_q=|G_q|$ ，则 $F_q(k)\le M_q$ ， $q^k\le M_q$ ，所以单项乘积、局部和分别满足

q^k\bigl(F_q(k)-F_q(k-1)\bigr)\le M_q^2, \qquad S_q\le M_q^2.

所有局部和的前缀乘积也不超过 $\prod_qM_q^2=\varphi(n)^2$ ，因此 answer *= subtotal 的中间结果同样安全。长度 $p^{e-1}(p-1)$ 的构造过程单调增长且最终不超过 $n$ ；计数递推的连乘不超过 $M_q$ 。

代码把长度、素因子、幂、计数、贡献和最终答案都存入 std::int64_t，乘法从操作数阶段就使用 64 位。试除条件写为 i64{p} * p > x，不依赖先做 32 位乘法再赋给 64 位变量。 $2$ 的幂也以 i64{1} 左移构造。对于当前 $n\le10^9$ 的界限，不必依赖非标准的 __int128；扩大范围时必须重做以上分析。

C++17 参考实现 #

下载完整 main.cpp · 运行说明 · 验证摘要

#include <cstdint>
#include <iostream>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

using i64 = std::int64_t;

std::vector<int> make_primes() {
    constexpr int limit = 31623;
    std::vector<bool> composite(limit + 1, false);
    std::vector<int> primes;
    for (int i = 2; i <= limit; ++i) {
        if (composite[i]) continue;
        primes.push_back(i);
        if (i64{i} * i <= limit) {
            for (int j = i * i; j <= limit; j += i) composite[j] = true;
        }
    }
    return primes;
}

std::vector<std::pair<i64, int>> factor(i64 x, const std::vector<int>& primes) {
    std::vector<std::pair<i64, int>> result;
    for (int p : primes) {
        if (i64{p} * p > x) break;
        if (x % p != 0) continue;
        int exponent = 0;
        do {
            x /= p;
            ++exponent;
        } while (x % p == 0);
        result.emplace_back(p, exponent);
    }
    if (x > 1) result.emplace_back(x, 1);
    return result;
}

i64 solve(i64 n, const std::vector<int>& primes) {
    if (n == 1) return 1;

    // freq[q][b] counts cyclic factors C_(q^b), with b >= 1.
    std::map<i64, std::vector<int>> freq;
    const auto add_cycle = [&](i64 length) {
        for (auto [q, b] : factor(length, primes)) {
            auto& counts = freq[q];
            if (static_cast<int>(counts.size()) <= b) counts.resize(b + 1, 0);
            ++counts[b];
        }
    };

    for (auto [p, e] : factor(n, primes)) {
        if (p == 2) {
            if (e >= 2) add_cycle(2);
            if (e >= 3) add_cycle(i64{1} << (e - 2));
        } else {
            i64 length = p - 1;
            for (int j = 1; j < e; ++j) length *= p;
            add_cycle(length);
        }
    }

    i64 answer = 1;
    for (const auto& [q, counts] : freq) {
        int active = std::accumulate(counts.begin(), counts.end(), 0);
        i64 previous = 1;
        i64 order = 1;
        i64 subtotal = 1;
        for (int k = 1; k < static_cast<int>(counts.size()); ++k) {
            order *= q;
            i64 current = previous;
            // F(k) / F(k-1) = q^(number of factors with exponent >= k).
            for (int j = 0; j < active; ++j) current *= q;
            subtotal += order * (current - previous);
            previous = current;
            active -= counts[k];
        }
        answer *= subtotal;
    }
    return answer;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    const auto primes = make_primes();
    int t;
    if (!(std::cin >> t)) return 0;
    while (t--) {
        i64 n;
        std::cin >> n;
        std::cout << solve(n, primes) << '\n';
    }
}

手算与样例 #

两个能揭示结构的例子 #

对 $n=48=16\cdot3$ ，单位群为 $C_2\times C_4\times C_2$ 。只有 $q=2$ 一个分量，指数列表为 $1,2,1$ ，因此

F_2(0)=1,\quad F_2(1)=8,\quad F_2(2)=16,

A(48)=1+2(8-1)+4(16-8)=47.

对 $n=54=2\cdot27$ ， $U(2)$ 不提供非平凡因子， $U(27)\cong C_{18}\cong C_2\times C_9$ 。于是

S_2=1+2(2-1)=3, \qquad S_3=1+3(3-1)+9(9-3)=61,

A(54)=3\cdot61=183.

两组原题样例 #

下表按原题的两组样例顺序列出。

样例组	输入 $n$ （按行）	输出（按行）
1	$1,5,8,54,9653618$	$1,11,7,183,9856882167209$
2	$48,2,4,8,16$	$47,1,3,7,23$

$n=2$ 时没有非平凡循环群因子，空乘积仍应为 $1$ 。 $n=8$ 时 $U(8)\cong C_2\times C_2$ ，答案是 $1+3\cdot2=7$ ；若误当成 $C_4$ ，就会错误地得到 $11$ 。

怎样验证这份实现 #

验证不仅比较样例，也避免让参考程序和正式实现复用同一个求和递推。

小规模直接差分。 对每个与 $n$ 互素的 $a$ ，从 $1$ 开始反复乘 $a$ 并取模，第一次回到 $1$ 时的次数就是阶。这种方法不使用单位群的结构分解，适合校验 $n=1$ 、奇素数幂、 $2$ 的幂和混合模数分支，但只在小范围使用。

大规模独立求和。 Python 参考程序使用任意精度整数，枚举 $L=\operatorname{lcm}(m_1,\ldots,m_r)$ 的约数 $d$ ，先计算

H(d)=\prod_j\gcd(d,m_j).

这是整个单位群中阶整除 $d$ 的元素数。随后在约数集合上做 Möbius 反演，恢复阶恰为 $d$ 的数量，再计算 $\sum_d d\,C(d)$ 。它不调用 C++ 求解器，也不使用逐素数的加权差分公式。两种算法共享单位群结构定理，结构分解的实现再由小规模直接差分检验。

固定随机种子 20260920，共 6411 条测试输入通过核对，覆盖两组样例、n=1..1000 穷举、小范围随机输入、素数幂与混合模数，以及四组各 1000 条的上界压力输入。

C++17 优化版和启用有符号溢出陷阱、标准库断言的检查版均通过测试，严格编译无警告。测试明细、压力输入与代码版本见验证摘要。

参考资料 #

QOJ 20240：Exponent：题面、约束与样例。
Codeforces Gym 106701：第二场比赛题目表。
赛方中文题解：Exponent 位于 PDF 第 3 页至第 4 页首行。
Conrad 的 CRT 与素数幂单位群讲义见前文链接，分别对应单位群的直积分解和循环因子结构。