乘法逆元定義：
b存在乘法逆元的充要條件是b與模數m互質 原因：b * x ≡ 1 (mod m) 如果b和m不互質，則 b * x肯定是m的倍數，b * x%m=0
所以b%m==0 ，b不存在乘法逆元
1.當n為質數時，可以用快速冪求逆元：
a / b（整除） ≡ a * x (mod m)
兩邊同乘b可得 a ≡ a * b * x (mod m) -> 1 ≡ b * x (mod m)
同 b * x ≡ 1 (mod m)
由費馬小定理可知，當m為質數時: b ^ (m - 1) ≡ 1 (mod m)
拆一個b出來可得 b * b ^ (m - 2) ≡ 1 (mod m)
所以當n為質數時，b的乘法逆元 x = b ^ (m - 2)%m
求a的乘法逆元：
import java.util.*; public class Main{ static long quick_pow(long a,long b,long c){ long res=1; while(b>0){ if((b&1)==1) res=res*a%c; a=a*a%c; b>>=1; } return res; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); int t=scan.nextInt(); while(t-->0){ long a=scan.nextLong(); long p=scan.nextLong(); if(a%p!=0) System.out.println(quick_pow(a,p-2,p)); else System.out.println("impossible"); } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93554.html
標籤：其他
上一篇：C語言遞回之二叉樹的最小深度
下一篇：擴展歐幾里得（模板）