题目链接
Atcoder方向
Luogu方向
题目解法
考虑等式两边都为多次齐次项
令等式左边的值为
F
(
x
,
y
,
z
)
F(x,y,z)
F(x,y,z)，等式右边的值为
G
(
x
,
y
,
z
)
G(x,y,z)
G(x,y,z)
当
F
(
x
,
y
,
z
)
≡
t
∗
G
(
x
,
y
,
z
)
(
m
o
d
p
)
F(x,y,z)\equiv t*G(x,y,z)\;(mod \;p)
F(x,y,z)≡t∗G(x,y,z)(modp)
因为等式左边比等式右边高一次
所以
F
(
x
t
,
y
t
,
z
t
)
≡
G
(
x
t
,
y
t
,
z
t
)
(
m
o
d
p
)
F(\frac{x}{t},\frac{y}{t},\frac{z}{t})\equiv G(\frac{x}{t},\frac{y}{t},\frac{z}{t})\;(mod\;p)
F(tx,ty,tz)≡G(tx,ty,tz)(modp)
由式子可以
t
=
F
(
x
,
y
,
z
)
∗
G
(
x
,
y
,
z
)
−
1
t=F(x,y,z)*G(x,y,z)^{-1}
t=F(x,y,z)∗G(x,y,z)−1
因为
t
≠
0
t\ne 0
t=0，所以
F
(
x
,
y
,
z
)
F(x,y,z)
F(x,y,z) 与
G
(
x
,
y
,
z
)
G(x,y,z)
G(x,y,z) 不等于
0
0
0，就一定有一组解
考虑没有解的情况出现概率较小（ < 1 4 <\frac{1}{4} <41），所以考虑随机 x , y , z x,y,z x,y,z 的值，直到找到一组合法的解
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
int qmi(int a,int b,int p){
int res=1;
for(;b;b>>=1){
if(b&1) res=res*a%p;
a=a*a%p;
}
return res;
}
void work(){
int n=read(),p=read();
while(true){
int x=rand()%(p-1)+1,y=rand()%(p-1)+1,z=rand()%(p-1)+1;
if(x==y||x==z||y==z) continue;
int xn=qmi(x,n,p),yn=qmi(y,n,p),zn=qmi(z,n,p);
int mi0=(x+y+z)%p,mi1=(xn+yn+zn)%p,mi2=(xn*xn%p+yn*yn%p+zn*zn%p)%p;
int Left=mi0*mi1%p*mi2%p,Right=(xn*xn%p*xn%p+yn*yn%p*yn%p+zn*zn%p*zn%p)%p;
// cout<<x<<' '<<y<<' '<<z<<' '<<mi0<<' '<<mi1<<' '<<mi2<<' '<<Left<<' '<<Right<<'\n';
if(!Right||!Left) continue;
int t=Right*qmi(Left,p-2,p)%p;
x=x*t%p,y=y*t%p,z=z*t%p;
// cout<<t<<'\n';
if(x>y) swap(x,y);
if(x>z) swap(x,z);
if(y>z) swap(y,z);
printf("%lld %lld %lld\n",x,y,z);
return;
}
}
signed main(){
srand(time(NULL));
int T=read();
while(T--) work();
return 0;
}
