2023NOIP A层联测9 长春花

题目大意

给定一个质数$p$，对于每个 0 ≤ x < p 0\leq x

0≤x<p，设$f(x)$表示最小的非负整数$a$，使得存在一个非负整数$b$，满足$(a^2+b^2)\mathrm{mod}p=x$。

求 max ⁡ { f ( 0 ) , f ( 1 ) , f ( 2 ) , … , f ( p − 1 ) } \max\{f(0),f(1),f(2),\dots,f(p-1)\} max{f(0),f(1),f(2),…,f(p−1)}的值。

$2\le p\le 10^5$，保证$p$为质数。

题解

题意即求一个最小的$mx$，使得对于每个 0 ≤ i < p 0\leq i

0≤i<p，都存在$0\le a\le mx$和 0 ≤ b < p 0\leq b

0≤b<p使得$(a^2+b^2)\mathrm{mod}p=i$。

我们可以试着打暴力，发现当$2\le p\le 10^5$且$p$为质数时，$mx$不超过$31$。所以，我们只需要从$0$到$31$枚举$a$，从$0$到$p-1$枚举$b$，并在$(a^2+b^2)\mathrm{mod}p$的位置上打上标记。当$0$到$p-1$都被打上标记时，当前的$a$即为答案。

时间复杂度为$O(n\cdot mx)$，其中$mx$为答案，$mx\le 31$。

code

#include
using namespace std;
int p,nd,v[100005];
int main()
{
	scanf("%d",&p);nd=p;
	for(int i=0;i<100;i++){
		for(int j=0;j<p;j++){
			int tmp=(1ll*i*i+1ll*j*j)%p;
			if(!v[tmp]){
				++v[tmp];--nd;
			}
		}
		if(!nd){
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20