2023NOIP A层联测9 长春花

2023-10-14 11:52
文章标签 联测 2023noip 长春花

本文主要是介绍2023NOIP A层联测9 长春花,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目大意

给定一个质数 p p p,对于每个 0 ≤ x < p 0\leq x<p 0x<p,设 f ( x ) f(x) f(x)表示最小的非负整数 a a a,使得存在一个非负整数 b b b,满足 ( a 2 + b 2 ) m o d p = x (a^2+b^2)\bmod p=x (a2+b2)modp=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(p1)}的值。

2 ≤ p ≤ 1 0 5 2\leq p\leq 10^5 2p105,保证 p p p为质数。


题解

题意即求一个最小的 m x mx mx,使得对于每个 0 ≤ i < p 0\leq i<p 0i<p,都存在 0 ≤ a ≤ m x 0\leq a\leq mx 0amx 0 ≤ b < p 0\leq b<p 0b<p使得 ( a 2 + b 2 ) m o d p = i (a^2+b^2)\bmod p=i (a2+b2)modp=i

我们可以试着打暴力,发现当 2 ≤ p ≤ 1 0 5 2\leq p\leq 10^5 2p105 p p p为质数时, m x mx mx不超过 31 31 31。所以,我们只需要从 0 0 0 31 31 31枚举 a a a,从 0 0 0 p − 1 p-1 p1枚举 b b b,并在 ( a 2 + b 2 ) m o d p (a^2+b^2)\bmod p (a2+b2)modp的位置上打上标记。当 0 0 0 p − 1 p-1 p1都被打上标记时,当前的 a a a即为答案。

时间复杂度为 O ( n ⋅ m x ) O(n\cdot mx) O(nmx),其中 m x mx mx为答案, m x ≤ 31 mx\leq 31 mx31

code

#include <bits/stdc++.h>
using namespace std;
int p, nd, v[100005];
int main() {freopen("A.in", "r", stdin);freopen("A.out", "w", stdout);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;
}

这篇关于2023NOIP A层联测9 长春花的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/210320

相关文章

NOIP2023模拟16联测37 大眼鸹猫

题目大意 有两个长度为 n n n的序列 a , b a,b a,b,这两个序列都是单调不降的。 你可以对 a a a进行不超过 m m m次操作,每次操作你可以选择一个 i i i满足 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n,然后选择一个整数(可以是负数) x x x,将 a i a_i ai​加上 x x x,这次操作要花费 x 2 x^2 x2的代价。 在操作的过程

NOIP2023模拟16联测37 总结

NOIP2023模拟16联测37 总结 T 1 T1 T1 求有多少区间的异或和为 k k k 的因子, n , k ≤ 1 0 5 n , k \le 10^5 n,k≤105 。看到异或就想到了前几天的拿到按位考虑的题目,想了半小时没想到。突然想前缀和,对每个 k k k 的因子记录一下 a ⊕ k a \oplus k a⊕k 的数量就好了 。 T 2 T2 T2 每次可以删去

NOIP2023模拟16联测37 D. 小猫吃火龙果

NOIP2023模拟16联测37 D. 小猫吃火龙果 文章目录 NOIP2023模拟16联测37 D. 小猫吃火龙果题目大意思路code 题目大意 有 n n n 个物品 A A A , B B B , C C C , A A A 吃 B B B, B B B 吃 C C C, C C C 吃 A A A,有两种操作,给 [ l , r ] [ l , r ]

2023.11.10联测总结

T 1 T1 T1求的是有多少个区间的异或和是 k k k的因子, n , k ≤ 1 0 5 n,k \leq 10^5 n,k≤105。 这道题用前缀和维护一下,暴力枚举所有区间就有 80 80 80分。 有一瞬间想过枚举因数,但是脑抽以为要 O ( n ) \mathcal O(n) O(n)枚举,然后就跑路了。 T 2 T_2 T2​给出一个有 n n n个数的数列,每次可以删去

2023NOIP A层联测28-大眼鸹猫

给你两个长度为 n n n 的序列 a , b a,b a,b,这两个序列都是单调不降的。 你可以对 a a a 进行不超过 m m m 次操作,每次操作你可以选择一个 i i i 满足 1 ≤ i ≤ n 1\le i\le n 1≤i≤n,然后选择一个整数(可以是负数) x x x,将 a i a_i ai​ 加上 x x x,这一次操作需要花费 x 2 x^2 x2 的代

NOIP2023模拟13联测34 B.competition

NOIP2023模拟13联测34 B.competition 文章目录 NOIP2023模拟13联测34 B.competition题目大意思路code 题目大意 现在有 n n n 个区间 [ l i , r i ] [l_i , r_i] [li​,ri​] ,现在问你选取若干的连续的区间的区间并的大小的和。 思路 设 p r e i , j pre_{i ,

NOIP2023模拟1联测22 爆炸

NOIP2023模拟1联测22 爆炸 题目大意 ​ 自己看 思路 当一个炸弹被引爆后,它的方向是固定的。如果被竖着引爆,那么应该选择横着引爆,否则选择竖着引爆,这是显然 的。 考虑对于每个炸弹 ( i , j ) (i , j) (i,j) 将第 i i i 行和第 j j j 列连边 对于每个水晶 ( i , j ) (i , j) (i,j) 如果 i i i 行和

NOIP2023模拟13联测34 competition

题目大意 有一场题目数量为 m m m的比赛,有一个团队想要来参加。 这个团队有 n n n个选手,编号为 i i i的选手能做第 l i ∼ r i l_i \sim r_i li​∼ri​道题,每题他都有 100 % 100\% 100%的概率做出来。 这个团队会随机派出一只队伍来参加这个比赛。 因为编号相邻的人关系更好,默契度也更高,所以一个团队派出的队伍一直都是编号为连续区间的选手

2023NOIP A层联测26-origen

给定 n n n 个整数 a 1 , a 2 … a n a_1,a_2\dots a_n a1​,a2​…an​,求 ∑ i = 1 n ∑ j = i n ( ⨁ k = i j a k ) 2 \sum\limits_{i=1}^n\sum\limits_{j=i}^n\left(\bigoplus\limits_{k=i}^{j}a_k\right)^2 i=1∑n​j=i∑n​(k

2023NOIP A层联测26-competition

现在有一个题目数量为 m m m 的比赛,有一个团队想要来参加。 这个团队有 n n n 位选手,编号为 i i i 的选手能做第 l i ∼ r i l_i\sim r_i li​∼ri​ 道题,每一道题他都有 100 % 100\% 100% 的概率能做出来。 这个团队会随机派出一支队伍来参加这个比赛。 因为编号相邻的人关系更好,默契度也更高,所以说一个团队派出的队伍一直都是编