P14102

费马小定理求逆元

难度 4 级 小学 算法入门 倍增 逆元
讨论 统计 29通过 45提交 64.4%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

费马小定理: 若 p 为素数,\gcd(a, p) = 1,则 a^{p - 1} \equiv 1 \pmod{p}。

另一个形式:对于任意整数 a,有 a^p \equiv a \pmod{p}。

给定一个数n和模数p,其中p是素数。求n在模p下的逆元

输入

一行,两个数字,分别表示n和p

输出

n在模p下的逆元

样例

样例 1
输入
4 7
输出
2

提示

0 < n < p < 2^{31} 。保证n和p互质

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交