Problem 4006 --阶(order)

4006: 阶(order)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $26$ 正确数量 $7$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

小多最近学习了一点数论。 

最近她学习了阶这个概念,对算阶很有兴趣。 

但是手算阶太难了,请你帮帮她。 

给定一个质数 p,定义一个数 x(1 ≤ x < p) 模 p 的阶为:最小的正整数 t 使得 xt 模 p 等于 1(即 xt 除以 p 的余数为 1),可以证明:这样的正整数一定存在。 

现在请你帮助小多算若干组阶。 

第一行一个正整数 T,代表接下来共有 T 个问题。 

接下来 T 行,每行两个正整数 p 和 x,请回答 x 模 p 的阶。 

输出共 T 行,对于每个问题,请输出一行一个正整数代表该问题的答案。
7
2 1
3 1
3 2
5 1
5 2
5 3
5 4
1
1
2
1
4
4
2

【样例 1 解释】 

以第一个和第五个为例。 第一个问题中 1 1 = 1,而 1 是最小的正整数,所以显然为答案。 第五个问题中 2 1 = 2, 2 2 = 4, 2 3 = 8 模 5 不为 1,2 4 = 16 模 5 为 1,因此 4 为答案。 

【数据规模与约定】 

对于 40% 的数据,满足 p ≤ 100。 

对于 70% 的数据,满足 p ≤ 104。 

对于 100% 的数据,满足 1 ≤ T ≤ 10, 1 ≤ x < p ≤ 105,保证 p 是质数。 

推荐代码 查看4006 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$7 $ms] chengcary 1090539 2024-04-02 10:47:56
内存最少[$2024 $KB] 只能过个样例~~~ 960235 2023-04-28 22:02:45
第一AC 只能过个样例~~~ 960235 2023-04-28 22:02:45
第一挑战 波士顿大龙虾 956821 2023-04-21 17:42:57

赛题来源/所属竞赛 “科大国创杯”2023年安徽省青少年信息学科普日活动小学组试题 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛