CSP模拟52联测14 A.长春花

本文主要是介绍CSP模拟52联测14 A.长春花，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CSP模拟52联测14 A.长春花

题目大意

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

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

思路

暴力搞一下发现 $a$ 很小，所以就预处理一下 $b[i^2\mathrm{mod}p]=1(i\in [0,p])$

然后就每个 $a$ 枚举一下就好了

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(long long x = y ; x <= z ; x ++)
using namespace std;
long long p , b[10000005];
int main () {freopen ("A.in" , "r" , stdin);freopen ("A.out" , "w" , stdout);scanf ("%d" , &p);fu (i , 1 , p) {b[(i * i) % p] = 1;}long long ans = 0;fu (i , 0 , p) {fu (j , 0 , p) {if (b[(1ll * (i + p) - 1ll * j * j % p) % p]) {ans = max (ans , j);break;}}}printf ("%d" , ans);return 0;
}

这篇关于CSP模拟52联测14 A.长春花的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---