#include<bits/stdc++.h>
using namespace std;

int p,ans;
bool buc[1000010];

int main(){
	cin >> p;
	for(int i = 0;i < p;i++){
		buc[(i * i) % p] = true;
	}
	for(int x = 0;x < p;x++){
		for(int a = 0;a < (p - 1) / 2;a++){
			if(buc[x - (a * a) % p]){
				ans = max(ans,a);
				break;
			}
		}
	}
	cout << ans;
	return 0;
}

代码如上，第二个样例输出12。

提供复杂度为O(n^3)的代码。

#include<bits/stdc++.h>
using namespace std;

int p;

int f(int x){
	for(int a = 0;a < p;a++){
		for(int b = a + 1;b < p;b++){
			int aa = a * a,bb = b * b;
			if((aa + bb) % p == x){
				return a;
			}
		}
	}
	return -1;
}

int main(){
	cin >> p;
	int ans = 0;
	for(int i = 1;i < p;i++){
		ans = max(ans,f(i));
	}
	cout << ans;
	return 0;
}