题目链接
原本看着式子直接晕了，觉得是高深的硬核数论，于是放弃（然后E也没想出来，sad）
关键的思路在于，考虑构造由(a,b,c)->(ta,tb,tc)这样的求解方式。
在看到这个做法后，会发现它很好地利用了题目齐次的性质；至于如何由齐次式想到这个做法，可能需要足够的天赋或者经验吧（悲）
化简后得到\(At\equiv B(\mod p)\)，那么只要A和B不为0 ，就可以得到一个非0的t，进而得到解！即要求得到一组(a,b,c)，满足在模p下：
（因为p是质数，故乘积为0等价于各个因式的并）
而题目又要求\(1\le a<b<c\le p-1\)，故很难直接构造出(a,b,c)，使得对于任意的p成立。
但又觉得在确定p的情况下，满足条件的三元组应该很多，所以考虑随机化；只需要证明随机一次不合法的概率有一个小于1的上界即可。
由于不知道各个因式的独立性如何，故考虑最弱的概率关系，即\(并\le和\)，考虑令每个式子均摊，只需证明:对任意整数k，随机一组(a,b,c)，\(a^k+b^k+c^k=0\)的概率小于\(1/4\)。三项单独考虑，先把\(a,b,c\)分别转成原根对应的次幂，那么每项的结果就是在长度\(p-1\)的环上每次走\(k\)步，共有\(d=\frac{p-1}{gcd(p-1,k)}\)种取值，根据\(d\)的大小分讨即可证明。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
int P;
inline int fpw(int a,int x){
int s=1;
for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
return s;
}
int n,a,b,c;
void inc(int& x,int y){
x+=y;
if(x>=P) x-=P;
if(x<0) x+=P;
}
int sum(int x,int y){
x+=y;
if(x>=P) x-=P;
if(x<0) x+=P;
return x;
}
void mul(int& x,int y){
x=1ll*x*y%P;
}
int prd(int x,int y){
return 1ll*x*y%P;
}
void Rand(){
unsigned int M=P-1;
a=rnd()%M+1;
b=rnd()%M+1;
c=rnd()%M+1;
}
int s0,s[4];
bool chk(){
if(a==b || b==c || a==c) return 0;
s0=sum(a,sum(b,c));
if(!s0) return 0;
for(int i=1;i<=3;i++){
int pw=1ll*n*i%(P-1);
s[i]=sum( fpw(a,pw),sum(fpw(b,pw),fpw(c,pw)) );
if(!s[i]) return 0;
}
//cout<<prd(s0,prd(s[1],s[2]))<<" "<<s[3]<<endl;
return 1;
}
int ans[4];
void work(){
scanf("%d%d",&n,&P);
Rand();
while(!chk()) Rand();
//puts("!");
int t=prd(s[3],fpw(s0,P-2));
for(int i=1;i<=2;i++) mul(t,fpw(s[i],P-2));
mul(a,t); mul(b,t); mul(c,t);
//chk();
//cout<<prd(s0,prd(s[1],s[2]))<<" "<<s[3]<<endl;
ans[1]=a; ans[2]=b; ans[3]=c;
sort(ans+1,ans+4);
printf("%d %d %d\n",ans[1],ans[2],ans[3]);
}
int main() {
int T; cin>>T;
while(T--) work();
return 0;
}