乘法逆元的版题的两种求解方法(费马小定理&&扩展欧几里得)

标签: 数论

例题

再竭衰庸定不支

题目描述

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

输入格式

一行两个正整数 n n n p p p

输出格式

n n n 行,第 i i i 行一个正整数,表示 i i i 在模 p p p 意义下的乘法逆元。

样例

样例输入

10 13

样例输出

1

7

9

10

8

11

2

5

3

4

费马小定理

思路

费马小定理:若 p p p 为质数,且 ( a , p ) = 1 (a,p) = 1 (a,p)=1 , $\rightarrow $ $ a ^{p - 1} \equiv 1 (\mod p)$

证:
∵ a p − 1 ≡ 1 ( m o d    p ) \because a^{p - 1} \equiv 1 (\mod p) ap11(modp)

∴ a p − 2 × a ≡ 1 ( m o d    p ) \therefore a^{p - 2} \times a \equiv 1 (\mod p) ap2×a1(modp)

∵ ( a , p ) = 1 \because (a, p) = 1 (a,p)=1

∴ a p − 2 ≡ a − 1 ( m o d    p ) \therefore a^{p - 2} \equiv a^{-1} (\mod p) ap2a1(modp)

代码
#include <cstdio>

long long n, p;

long long ksm(long long a, long long b){
	long long ans = 1;
	while(b){
		if(b & 1)ans = (long long)(ans * a) % p;
		a = (long long) (a * a) % p;
		b >>= 1;
	}
	return ans;
}

long long inv(long long a){
	return ksm(a, p - 2) % p;
}
int main() {
	scanf("%lld %lld", &n, &p);
	for(int i = 1; i <= n; i ++){
		printf("%lld\n", inv(i));
	}
	return 0;
} 

扩展欧几里得

思路

扩展欧几里得:在已知 a , b ( a , b ∈ Z + ) a, b(a, b\in\mathbb Z^+) a,b(a,bZ+)的情况下,求不定方程 a x + b y = ( a , b ) ax + by = (a, b) ax+by=(a,b)的一组整数解,则 ∃ x , y ∈ Z \exists x, y \in \mathbb Z x,yZ使贝祖等式 a x + b y = ( a , b ) ax + by = (a, b) ax+by=(a,b) 成立

证:
∵ ∃ x , y ∈ Z \because \exists x, y \in \mathbb Z x,yZ使贝祖等式 a x + b y = ( a , b ) ax + by = (a, b) ax+by=(a,b) 成立

∴ a x ≡ 1 ( m o d    p ) = a x − p y = 1 \therefore ax \equiv 1 (\mod p) = ax - py = 1 ax1(modp)=axpy=1

代码
#include <cstdio>

long long n, p;
long long x, y;

long long ex_gcd(long long a, long long b){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
	int Gcd = ex_gcd(b, a % b);
	long long t = x;
	x = y;
	y = t - (a / b) * y;
	return Gcd;
}

long long inv(long long a, long long b){
	long long flag = ex_gcd(a, b);
	return (flag == 1 ? (x % b + b) % b : -1); 
}

int main() {
	scanf("%lld %lld", &n, &p);
	for(int i = 1; i <= n; i ++){
		printf("%lld\n", inv(i, p));
	}
	return 0;
} 

关于两者时间复杂度的直观对比

这是不加任何优化的

扩欧

扩欧时间.png

费马

费马版时间.png

版权声明:本文为DYNHlalalalala原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/DYNHlalalalala/article/details/109397572