长春花题解

题意概述

给定一个素数 \(p\)，对每个 \(0 \le x < p\)，设 \(f(x)\) 表示一个最小的非负整数 \(a\)，使得存在一个非负整数 \(b\)，满足 \((a^2+b^2) \bmod p = x\)。

现在，你想要求 \(\max\{ f(0), f(1), \cdots, f(p-1) \}\) 的值。

输入格式

输入只有一行，包含一个整数 \(p\)。保证 \(p\) 为素数。

输出格式

输入只有一行，包含一个整数 \(p\)。保证 \(p\) 为素数。

样例一

输入

\(7\)

输出

\(2\)

样例二

输入

\(233\)

输出

\(10\)

思路概述

考场上的时候满脑子都是同余方程，扩展欧几里得，一直以为是一道书论题，还以为暴力都和同余有点关系，根本没往这方面想，最后才想到这“暴力”，其实看大样例不难发现，质数很大的时候a的值也才十几，那不妨跑一下最大的质数， \(1e5\) 的，发现也才三十多，所以这时候就可以放心跑了，\(a\) 可以开到 \(50\)，保险 \(100\) 也行，\(b\) 按时间开到最大即可，最后直接找这些余数的答案就行

code

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

const int N=5e5+10;
int p,ans[N],maxx;

int main()
{
	scanf("%d",&p);
	memset(ans,0x3f,sizeof ans);
	for(int i=1;i<=40;i++)
	{
		for(int j=0;j<=5e4;j++)
		{
			int k=(1ll*i*i+1ll*j*j)%p;
			ans[k]=min(ans[k],i);
		}
	}
	for(int i=0;i<p;i++)maxx=max(maxx,ans[i]);
	cout<<maxx;
	return 0;
}