Problem Statement
You are given a positive integer $n$, and a prime number $p$ at least $5$.
Find a triple of integers $(x,y,z)$ that satisfies all of the following conditions.
- $1\leq x < y < z \leq p - 1$.
- $(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) \equiv x^{3n}+y^{3n}+z^{3n}\pmod{p}$.
It can be proved that such a triple $(x,y,z)$ always exists.
You have $T$ test cases to solve.
Constraints
- $1\leq T\leq 10^5$
- $1\leq n\leq 10^9$
- $p$ is a prime number satisfying $5\leq p\leq 10^9$.
Input
The input is given from Standard Input in the following format:
$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$
Each case is in the following format:
$n$ $p$
Output
Print $T$ lines. The $i$-th line should contain $x,y,z$ with spaces in between where $(x,y,z)$ is a solution for the $i$-th test case.
If multiple solutions exist, you may print any of them.
Sample Input 1
3 1 7 2 7 10 998244353
Sample Output 1
1 4 6 1 2 5 20380119 21549656 279594297
For the first test case:
- $(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}) = (1+4+6)(1+4+6)(1+16+36) = 6413$, and
- $x^{3n}+y^{3n}+z^{3n} = 1 + 64 + 216 = 281$.
We have $6413\equiv 281\pmod{7}$, so the conditions are satisfied.
本来以为拆开有什么用，后来又发现没有。
但是观察到两边是不齐次的，也就是说，如果设 \(x=ta%p,y=tb%p,z=tc%p\)，那么我们可以随机出一个 \(a,b,c\)，然后是可以解出 \(t\) 的
具体而言，设算出来左式= \(t^{6n}\times d\)，右式为 \(t^{3n}\times e\)，那么知道了 \(d\) 和 \(e\)，可以解出 \(t\)
那么 \(d\) 和 \(e\) 要满足什么要求可以解出 \(t\) 呢？只要不都是 0 就行了。随机出来 \(a,b,c\)，就可以算出 \(d\) 和 \(e\)，容易发现，\(d\) 和 \(e\) 大概率不是0.
#include<bits/stdc++.h>
using namespace std;
int n,p,TME;
long long x,y,z,a,b,c,d,e,f,g;
mt19937_64 gen(time(0)) ;
long long pw(int x,long long y)
{
if(!y)
return 1;
long long t=pw(x,y>>1);
if(y&1)
return t*t%p*x%p;
return t*t%p;
}
int main()
{
scanf("%d",&TME);
while(TME--)
{
scanf("%d%d",&n,&p);
while(1)
{
x=gen()%(p-1)+1,y=gen()%(p-1)+1,z=gen()%(p-1)+1;
if(x^y&&y^z&&z^x&&(x+y+z)%p&&(a=pw(x,n)+pw(y,n)+pw(z,n))%p&&(b=pw(x,n+n)+pw(y,n+n)+pw(z,n+n))%p&&(c=pw(x,n*3LL)+pw(y,n*3LL)+pw(z,n*3LL))%p)
{
d=(x+y+z)%p*a%p*b%p;
c=c*pw(d,p-2)%p;
e=c*x%p,f=c*y%p,g=c*z%p;
if(e>f)
swap(e,f);
if(e>g)
swap(e,g);
if(f>g)
swap(f,g);
printf("%lld %lld %lld\n",e,f,g);
break;
}
}
}
}