求乘法逆元的两种方法（费马小定理）（JAVA）

浅浅的花香味﹌ 2023-01-10 14:52 145阅读 0赞

### 目录 ###

*   *  引入：
     *  分析：
     *  费马小定理求逆元（logn）
     *   *  代码：
     *  初始化1~n对p的逆元（N）
     *   *  代码：

## 引入： ##

[题目链接][Link 1].

给定 n,p 求 1∼n 中所有整数在模 p 意义下的乘法逆元。

## 分析： ##

inv(a)表示元素a在p下的逆元

具体形式为  i n v ( a ) ∗ a % p = 1 inv(a)\*a\\%p=1 inv(a)∗a%p=1

## 费马小定理求逆元（logn） ##

限制条件：p必为质数才可以用，否则答案具有不确定性

费马小定理 定义： a p − 1 % p = 1 a^\{p-1\}\\%p=1 ap−1%p=1  
可以推出： a p − 2 ∗ a % p = 1 a^\{p-2\}\*a\\%p=1 ap−2∗a%p=1  
即: i n v ( a ) = a p − 2 inv(a)=a^\{p-2\} inv(a)=ap−2  
所以用快速幂求一下，在运行过程中对p取模即可。

### 代码： ###

JAVA语言限制无法通过，换C也不一定能AC，

因为本题有n次询问

总复杂度O(nlogn)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

import java.util.Scanner;
    
    public class 求逆元费马小定理 { 
    	static long n, p;
    	static long pow(long m, long n) { 
    		long res = 1, A = m;
    		while (n != 0) { 
    			if ((n & 1) == 1) { 
    				res = res * A % p;
    			}
    			A = A * A % p;
    			n >>= 1;
    		}
    		return res;
    	}
    
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextLong();
    		p = sc.nextLong();
    		for (int i = 1; i <= n; i++) { 
    			System.out.println(pow(i, p - 2));
    		}
    	}
    }

## 初始化1~n对p的逆元（N） ##

限制条件：适用于对同一个p求多个a的逆元

已知 p/i=k; p%i=r;  
 p = k ∗ i + r ； （ 0 < r < p ） p=k\*i+r；（0<r<p） p=k∗i\+r；（0<r<p）  
即： ( k ∗ i + r ) % p = 0 ; (k\*i+r)\\%p=0; (k∗i\+r)%p=0;  
两边同时乘 inv( i ) \* inv( r ): ( k ∗ i + r ) ∗ i n v ( i ) ∗ i n v ( r ) % p = 0 ∗ i n v ( i ) ∗ i n v ( r ) = 0 ; (k\*i+r)\*inv(i)\*inv(r)\\%p=0\*inv(i)\*inv(r)=0; (k∗i\+r)∗inv(i)∗inv(r)%p=0∗inv(i)∗inv(r)=0;  
将i与r的逆元放入小括号： ( k ∗ i n v ( r ) + i n v ( i ) ) % p = 0 ; (k\*inv(r)+inv(i))\\%p=0; (k∗inv(r)\+inv(i))%p=0;  
分离出inv(i) i n v ( i ) % p = ( − k ∗ i n v ( r ) ) % p inv(i)\\%p=(-k\*inv(r))\\%p inv(i)%p=(−k∗inv(r))%p  
 = ( − p / i ∗ i n v ( p % i ) ) % p =(-p/i\*inv(p\\%i))\\%p =(−p/i∗inv(p%i))%p  
 = p ∗ i n v ( p % i ) % p − p / i ∗ i n v ( p % i ) % p =p\*inv(p\\%i)\\%p-p/i\*inv(p\\%i)\\%p =p∗inv(p%i)%p−p/i∗inv(p%i)%p  
 = ( p − p / i ) ∗ i n v ( p % i ) % p =(p-p/i)\*inv(p\\%i)\\%p =(p−p/i)∗inv(p%i)%p  
因为i的逆元inv(i)<p所以： i n v ( i ) % p = i n v ( i ) = ( p − p / i ) ∗ i n v ( p % i ) % p inv(i)\\%p=inv(i)=(p-p/i)\*inv(p\\%i)\\%p inv(i)%p=inv(i)=(p−p/i)∗inv(p%i)%p

### 代码： ###

JAVA语言限制无法通过所有样例，换成C即可AC；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]

import java.util.Scanner;
    
    public class Main { 
    	public static long inv[]=new long[3000005],n,p;
    	public static void Init(){ 
    		inv[1]=1;
    		for(int i=2;i<=n;i++){ 
    			inv[i]=(p-p/i)*inv[(int)p%i]%p;
    		}
    	}
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		n=sc.nextInt();p=sc.nextInt();
    		Init();
    		for(int i=1;i<=n;i++){ 
    			System.out.println(inv[i]);
    		}
    	}
    }

[Link 1]: https://www.luogu.com.cn/problem/P3811
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20221119/d5dcca7000ff4f97ad6aa2e88e297a97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210125172450840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70