企业官网建设流程全解析

题目描述

给定一个素数ppp和一个常数0<a<p0 < a < p0<a<p。求所有满足x3≡a(modp)x^3 \equiv a \pmod px3≡a(modp)的xxx。

输入格式

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

输出格式

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

样例

输入

2 31

输出

4 7 20

题目分析

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

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

解题思路

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

1. 初始化一个布尔标记，用于控制输出时数字之间的空格格式。
2. 使用循环变量xxx从000遍历到p−1p-1p−1。
3. 计算x3 mod px^3 \bmod px3modp，由于p<1000p < 1000p<1000，可直接使用646464位整数（如long long\texttt{long long}long long）避免溢出，不过实际上10003=1091000^3 = 10^910003=109仍在323232位整数范围内，但为了安全仍用long long\texttt{long long}long long。
4. 若计算结果等于aaa，则输出xxx，并在后续输出前添加空格分隔。
5. 遍历结束后输出换行。若没有任何xxx满足条件，则直接输出空行。

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

代码实现

// 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>usingnamespacestd;intmain(){inta,p;while(cin>>a>>p){boolfirst=true;for(intx=0;x<p;++x){if((1LL*x*x*x)%p==a){if(!first)cout<<' ';cout<<x;first=false;}}cout<<'\n';}return0;}

总结

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