C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2022-08-16 11:56:56

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
ll w ;
struct P
{
	ll x,y ;
};
P mul(const P &a,const P &b,ll p)
{
	P res ;
	res.x=(a.x*b.x+a.y*b.y%p*w)%p ;
	res.y=(a.x*b.y+a.y*b.x)%p ;
	return res ;
}
P P_qsm(P a,ll b,ll mod)
{
	P ans={1,0} ;
	while(b)
	{
		if(b&1) ans=mul(ans,a,mod) ;
		a=mul(a,a,mod) ; b>>=1 ;
	}
	return ans ;
}
ll qsm(ll a,ll b,ll mod)
{
	ll ans=1 ;
	while(b)
	{
		if(b&1) ans=ans*a%mod ;
		a=a*a%mod ; b>>=1 ;
	}
	return ans ;
}
mt19937 mt(time(0)) ;
ll Legendre(ll a,ll p) { return qsm(a,(p-1)>>1,p) ; }
ll equation_solve(ll b,ll p)
{
	if(p==2) return 1 ;
	if((Legendre(b,p)+1)%p==0) return -1 ;
	ll a ;
	while(1)
	{
		a=uniform_int_distribution<ll>(0,p-1)(mt) ;
		//a=rand()%p ;
		w=((a*a-b)%p+p)%p ;
		if((Legendre(w,p)+1)%p==0)
			break ;
	}
	return P_qsm({a,1},(p+1)>>1,p).x ;
}
int main()
{
	int T=1 ; 
	while(T--)
	{
		ll a,p ;
		cin>>p>>a ;
		a=a%p ;
		ll x=equation_solve(a,p) ;
		if(x==-1) puts("No Solution") ;
		else
		{
			ll y=p-x ;
			if(x==y) cout<<x<<'\n' ;
			else cout<<min(x,y)<<' '<<max(x,y)<<'\n' ;
		}
	}
	return 0 ;
}

C++ 解法, 执行用时: 13ms, 内存消耗: 572K, 提交时间: 2022-01-16 18:21:23

#include <stdio.h>
int main()
{
	int x=1,p,a;
	scanf("%d %d",&p,&a);
	int mod=0,flag=0;
	for(x=0;x<p;x++){
		mod=(2*x+1+mod)%p;
		if(mod==a){
			flag=1;
			printf("%d ",x+1);
		}
	}
	if(flag==0) printf("No Solution");
	return 0;
}