E · Exponent：中文题面与个人代码

本场总览 · QOJ 原题

时限 1 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

给定正整数 $n$ 。对每个 $1\le a\le n$ ，定义 $\operatorname{ord}_n(a)$ 为使 $a^x\equiv1\pmod n$ 成立的最小正整数 $x$ ；若不存在，定义为零。求

$\sum_{a=1}^{n}\operatorname{ord}_n(a).$

题目开头提到的“群的指数”是所有元素阶的最小公倍数，但本题要求的是阶之和，不要混淆。

输入、输出与约束 #

先输入 $1\le T\le10^3$ ，接下来每组一个整数 $1\le n\le10^9$ 。每组输出一个整数答案，不取模。当 $n=1$ 时，唯一元素满足所有正指数的同余条件，最小正指数为 $1$ ，答案为 $1$ 。

样例 #

输入 1 #

输出 1 #

1
11
7
183
9856882167209

输入 2 #

输出 2 #

样例说明 #

例如 $n=5$ 时， $a=1,2,3,4,5$ 的贡献分别为 $1,4,4,2,0$ ，总和 $11$ 。 $n=8$ 时，可逆元素 $1,3,5,7$ 的阶为 $1,2,2,2$ ，总和 $7$ ；偶数贡献零。第二组样例包含 $2$ 的幂，专门提醒其单位群结构不能直接套用奇素数幂的结论。

个人代码：只完成了筛法预处理 #

本页的 E.cpp 是原始个人尝试。N 约为 $\sqrt{10^9}+5$ ；pri 保存小于 N 的素数，vis 标记合数，v[j] 保存 $j$ 的不同素因子。外层扫描到未标记的 $i$ 时确认其为素数，再给所有倍数的因子表加入 $i$ 。

筛法预处理时间为 $O(N\log\log N)$ ，因子表总空间同阶；每组 solve() 读取 n，随后仅有一个空的素数循环，没有分解当前 $n$ 、求元素阶或输出答案的逻辑。这份程序即使顺利结束，也没有完成题目。

本地结果： C++17 编译成功；两组样例均没有任何输出；边界 $n=1$ 也为空输出。本页不把“能编译”记为“通过”。

与完整参考解分开阅读 #

Exponent 完整参考题解及其 C++17 参考实现是另一份已整理、已做本地验证的实现，不是这里的个人 E.cpp。参考解利用 CRT 拆单位群，再按素数分量统计元素阶；请按元素阶 → 模 n 单位群 → 完整题解的顺序阅读。E 题赛中未通过，赛后 OJ 提交结果仍待补。

原始 C++ 文件 #

下载 E.cpp · 验证说明

下面展示原稿，保留未完成部分和已发现问题；下载文件保留原始字节。SHA-256：83c33dbc16b9aa3f5bfe5a441aa2639095e59e8b9b2cf67ad847c9203208ff5b。

#include <bits/stdc++.h>
using namespace std;

const int N=(int)sqrt(1e9)+5;
int pri[N],n,tot,vis[N];
vector<int>v[N];
void solve()
{
    cin>>n;
    for(int j=1;j<=tot;j++)
    {

    }
    return;
}
void init()
{
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            pri[++tot]=i;
            for(int j=i;j<N;j+=i)
                v[j].push_back(i),vis[j]=1;
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin>>T;
    init();
    while(T--)solve();    
    return 0;
}