首页
A
wzkole12
当前主题：自动模式
查看保存队列
搜索
专栏文章
P12540 题解
V
Vitamin_B
2025/05/19 15:51
P12540
题解
参与者 2
已保存评论 2
文章操作
快速查看文章及其快照的属性，并进行相关操作。
当前评论
2 条
当前快照
1 份
快照标识符
@mip994kq
此快照首次捕获于
2025/12/03 08:14
3 个月前
此快照最后确认于
2025/12/03 08:14
3 个月前
查看原文
时光机
更新文章
复制链接
复制快照链接
复制正文 Markdown
前置知识
你需要知道：对于每个素数
p
p
p
和
1
≤
x
<
p
1\le x<p
1
≤
x
<
p
的整数，都有
x
p
−
1
≡
1
(
m
o
d
p
)
,
(
p
−
1
)
≡
−
1
(
m
o
d
p
)
x^{p-1}\equiv1\pmod p,(p-1)\equiv -1\pmod p
x
p
−
1
≡
1
(
mod
p
)
,
(
p
−
1
)
≡
−
1
(
mod
p
)
。
题解
我们只需要取
b
=
(
p
−
1
)
2
b=(p-1)^2
b
=
(
p
−
1
)
2
即可。
左式：
a
[
(
p
−
1
)
2
]
≡
1
p
−
1
≡
1
(
m
o
d
p
)
a^{[(p-1)^2]}\equiv1^{p-1}\equiv1\pmod p
a
[(
p
−
1
)
2
]
≡
1
p
−
1
≡
1
(
mod
p
)
。
右式：
[
(
p
−
1
)
2
]
c
≡
[
(
−
1
)
2
]
c
≡
1
c
≡
1
(
m
o
d
p
)
[(p-1)^2]^c\equiv[(-1)^2]^c\equiv1^c\equiv1\pmod p
[(
p
−
1
)
2
]
c
≡
[(
−
1
)
2
]
c
≡
1
c
≡
1
(
mod
p
)
。
相关推荐
评论
共 2 条评论，欢迎与作者交流。
最新优先
最早优先
搜索
正在加载评论...