UVa 13197 Cuberoot This

题目描述

给定一个素数 $p$ 和一个常数 $0<a<p$ 。求所有满足 $x^3\equiv a(\mathrm{mod}p)$ 的 $x$ 。

输入格式

每行一组数据（最多 $1000$ 组），包含两个整数 $a$ 和 $p$ ，其中 $p$ 是素数且 $p<1000$ 。输入直到文件结束。

输出格式

对于每组数据，按升序输出所有满足条件的 $x$ （ $0\le x<p$ ），每个数之间用一个空格隔开，输出占一行。如果没有解，则输出一个空行。

样例

输入

2 31

输出

4 7 20

题目分析

本题要求解模素数 $p$ 下的立方同余方程 $x^3\equiv a(\mathrm{mod}p)$ 。由于 $p$ 是素数，且 $p<1000$ ，数据范围非常小，可以直接采用暴力枚举的方法，遍历所有可能的 $x$ 值（ $0$ 到 $p-1$ ），验证是否满足同余式。

暴力枚举的时间复杂度为 $O(p)$ ，而每组输入的 $p$ 不超过 $1000$ ，最多 $1000$ 组输入，总计算量不超过 $10^6$ 次模乘运算，在 $\text{C++}$ 中可以在极短时间内完成。因此，本题不需要利用数论中的原根、离散对数等高级理论，简单的枚举即可通过。

解题思路

对于每一组输入 $(a,p)$ ，执行以下步骤：

由于 $p$ 是素数，但本算法并不依赖该性质，对于任意正整数 $p$ 同样有效（只要 $a$ 在合理范围内），因此具有通用性。

代码实现

// Cuberoot This
// UVa ID: 13197
// Verdict: Accepted
// Submission Date: 2026-06-24
// UVa Run Time: 0.010s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

int main() {
int a, p;
while (cin >> a >> p) {
bool first = true;
for (int x = 0; x < p; ++x) {
if ((1LL * x * x * x) % p == a) {
if (!first) cout << ' ';
cout << x;
first = false;
}
}
cout << '\\n';
}
return 0;
}

总结

• 本题核心在于观察到数据范围极小，从而选择最直接的暴力枚举解法，无需复杂数论知识。
• 枚举所有 $x$ 并检验同余式，代码简洁，易于实现。
• 输出格式控制是本题的一个小细节，需要注意多个答案之间的空格分隔以及无解时的空行输出。
• 该解法的时间复杂度为 $O(\sum p)$ ，空间复杂度为 $O(1)$ ，在给定限制下完全可行。当 $p$ 较大时，需要利用数论性质（如三次剩余）优化，但本题并无此要求。