摘要
Title: 876. 快速幂求逆元
Tag: 费马小定理、快速幂、逆元
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

876. 快速幂求逆元

• 题意

  给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。
  注意：请返回在 0∼p−1 之间的逆元。

• 思路

  $ax \equiv 1(modn)$ 若a是n的倍数，那么肯定不存在逆元

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-10 21:30:59
  FilePath: \ACM\Acwing\876.py
  LastEditTime: 2022-03-10 21:31:00
  '''
  for _ in range(int(input())):
      a, p = map(int, input().split())
      if a % p == 0:
          print("impossible")
      else:
          print(pow(a, p - 2, p))