C++(g++ 7.5.0) 解法, 执行用时: 15ms, 内存消耗: 496K, 提交时间: 2022-09-07 12:22:52

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline bool read(T&x){
x=0;char c=getchar();int f=1;while(!isdigit(c)&&(c!='-')&&(c!=EOF))c=getchar();
if(c==EOF)return 0;if(c=='-')f=-1,c=getchar();
while(isdigit(c)){x=x*10+(c&15);c=getchar();}x*=f;return 1;
}template<typename T,typename...Args>inline bool read(T&x,Args&...args){bool res=1;res&=read(x);res&=read(args...);return res;}
typedef long long LL;typedef unsigned long long u64;typedef unsigned u32;typedef long double LD;typedef pair<int,int> pii;typedef pair<LL,LL> pll;
#define pln putchar('\n')
#define For(i,a,b)  for(int i=(a),(i##i)=(b);i<=(i##i);++i)
#define Fodn(i,a,b) for(int i=(a),(i##i)=(b);i>=(i##i);--i)
const int M=1000000007,INF=0x3f3f3f3f;const long long INFLL=0x3f3f3f3f3f3f3f3fLL;
const int N=1000009;

struct Square_root{
    typedef int DAT;//操作数类型
    const DAT P;DAT I2;Square_root(DAT p=1):P(p){}
    #define X first
    #define Y second
    DAT mul(DAT a,DAT b)const{return (LL)a*b%P;}  //DAT=int
    //DAT mul(DAT a,DAT b)const{u64 r=(u64)a*b-(u64)((LD)a/P*b+0.5L)*P;return r<P?r:r+P;}  //DAT=long long
    typedef pair<DAT,DAT> pii;
    pii mul(pii a,pii b)const{return{(mul(a.X,b.X)+mul(mul(I2,a.Y),b.Y))%P,(mul(a.X,b.Y)+mul(a.Y,b.X))%P};}
    template<class T>T pow(T a,DAT b,T x){for(;b;b/=2,a=mul(a,a))if(b&1)x=mul(x,a);return x;}
    DAT operator()(DAT n){//传入非负整数 求最小非负解 无解返回-1
        if((n%=P)<=1)return n;
        if(pow(n,(P-1)/2,(DAT)1)==P-1)return -1;
        DAT a;do a=rand();while(pow(I2=(mul(a,a)-n+P)%P,(P-1)/2,(DAT)1)==1);//随机化可能寄
        DAT x=pow(pii{a,1},(P+1)/2,{1,0}).X;return min(x,P-x);
    }
    #undef X
    #undef Y
};

struct Cube_root{
    typedef int DAT;//操作数类型
    const DAT n,p;Cube_root(DAT _n=1,DAT _p=1):n(_n%_p),p(_p){};//传参接口 求解 x^3 = n (mod p)
    struct Z3{DAT x,y,z;};
    DAT mul(DAT a,DAT b)const{return (LL)a*b%p;}  //DAT=int
    //DAT mul(DAT a,DAT b)const{u64 r=(u64)a*b-(u64)((LD)a/p*b+0.5L)*p;return r<p?r:r+p;}  //DAT=long long
    Z3 mul(Z3 a,Z3 b)const{return(Z3){
        (mul(a.x,b.x)+mul((mul(a.y,b.z)+mul(a.z,b.y))%p,n))%p,
        ((mul(a.x,b.y)+mul(a.y,b.x))%p+mul(mul(a.z,b.z),n))%p,
        ((mul(a.x,b.z)+mul(a.y,b.y))%p+mul(a.z,b.x))%p
    };}
    template<class T>T pow(T a,DAT b,T x){for(;b;b/=2,a=mul(a,a))if(b&1)x=mul(x,a);return x;}
    DAT operator()(){ //求某个非负解 无解返回-1 (并不能对一般n求最小非负解)
        if(n==0||p<=3)return n;
        if(p%3==2)return pow(n,(2*p-1)/3,(DAT)1);
        if(pow(n,(p-1)/3,(DAT)1)!=1)return -1;
        Z3 r;do r=pow((Z3){rand(),rand(),rand()},(p-1)/3,(Z3){1,0,0});while(r.x!=0||r.y==0||r.z!=0);//随机化可能寄
        return pow(r.y,p-2,(DAT)1);
    }
};

int p,a;

inline void solve(int T){
    //printf("Case #%d: ",T);
    read(p,a);
    assert(a>0);
    if(p<=3){
        printf("%d\n",a);
        return;
    }
    int x=Cube_root(a,p)();
    if(x==-1){
        puts("No Solution");
        return;
    }
    if(p%3==2){
        printf("%d\n",x);
        return;
    }
    int e=Square_root(p)(p-3)-1;
    if(e<0)e+=p;
    if(e%2==0)e/=2;else e=e*(p+1ll)/2%p;
    set<int>q;q.insert({x,int(LL(x)*e%p),int(LL(x)*e%p*e%p)});
    for(auto it:q)printf("%d ",it);pln;
}

signed main(){
    int t;read(t);
    for(int i=1;i<=t;++i)solve(i);
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 13ms, 内存消耗: 504K, 提交时间: 2023-08-12 16:52:06

#include<bits/stdc++.h>
#define int long long
using namespace std;
int qz(int x,int y,int z){
	int res=1;
	for(;y;y>>=1){
		if(y&1) res=res*x%z;
		x=x*x%z;
	}
	return res;
}
namespace Cipolla{
	int mod,I_mul_I;
	struct Complex{
		int real,imag;
		Complex(int real=0,int imag=0):real(real),imag(imag){}
		bool operator == (const Complex &x) const{
			return x.real==real&&x.imag==imag;
		}
		Complex operator * (const Complex &x) const{
			return Complex((x.real*real+I_mul_I*x.imag%mod*imag)%mod,(x.imag*real+x.real*imag)%mod);
		}
	};
	Complex Qz(Complex x, int y) {
		Complex res=1;
		for(;y;y>>=1){
			if(y&1) res=res*x;
			x=x*x;
		}
		return res;
	}
	bool check(int x){
		return Qz(x,mod-1>>1)==1;
	}
	void solve(int n,int p,int &x0,int &x1){
		mod=p;
		if(!n){
			x0=x1=0;
			return ;	
		}
		if(!check(n)){
			x0=x1=-1;
			return ;
		}
		int a=rand()%mod;
		while(!a||check((a*a+mod-n)%mod)) a=rand()%mod;
		I_mul_I=(a*a+mod-n)%mod;
		x0=Qz(Complex(a,1),mod+1>>1).real;
		x0=min(x0,mod-x0);
		x1=mod-x0;
	}
}
namespace CubeRoot{
	int n,mod,w;
	struct Complex{
		int x,y,z;
		Complex(int x,int y,int z):x(x),y(y),z(z) {}
		Complex operator * (const Complex &a) const{
			return Complex((a.x*x+a.y*z%mod*n+a.z*y%mod*n)%mod,
            (a.x*y+a.y*x+a.z*z%mod*n)%mod,
            (a.x*z+a.y*y+a.z*x)%mod);
		}
	};
	Complex Qz(Complex x,int y){
		Complex res={1,0,0};
		for(;y;y>>=1){
			if(y&1) res=res*x;
			x=x*x;
		}
		return res;
	}
	void solve(int _n,int p,int &x0,int &x1,int &x2){
		n=_n,mod=p;
		x0=x1=x2=-1;
		if(!n||mod==2||mod==3){
			x0=n;
			return ;
		} 
		if(mod%3==2){
			x0=qz(n,(2*mod-1)/3,mod);
			return ;
		}
		if(qz(n,(mod-1)/3,mod)!=1) return ;
		int temp;
		Cipolla::solve(mod-3,mod,w,temp);
		w=(w-1)*(mod+1>>1)%mod;
		while(1){
			Complex v(rand()%mod,rand()%mod+1,rand()%mod+1);
			v=Qz(v,(mod-1)/3);
			if(v.x==0&&v.z==0) {
                x0=qz(v.y,mod-2,mod);
                x1=x0*w%mod;
                x2=x1*w%mod;
                break;
            }
		}
	}
}
signed main(){
	srand(unsigned(time(0)));
	int t,a,p;
	cin>>t;
	while(t--){
		cin>>p>>a;
		int x[3];
		CubeRoot::solve(a,p,x[0],x[1],x[2]);
		if(x[0]==-1) cout<<"No Solution\n";
		else if(x[1]==-1) cout<<x[0]<<'\n';
		else{
			sort(x,x+3);
			cout<<x[0]<<' '<<x[1]<<' '<<x[2]<<'\n';
		}
	}
	return 0;
}