例题

再竭衰庸定不支

题目描述

给定正整数 n n n 与 p p p ，求 1 − − n 1--n 1−−n 中的所有数在模 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) ∵ap−1≡1(modp)

∴ a p − 2 × a ≡ 1 ( m o d    p ) \therefore a^{p - 2} \times a \equiv 1 (\mod p) ∴ap−2×a≡1(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) ∴ap−2≡a−1(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,b∈Z+)的情况下，求不定方程 a x + b y = ( a , b ) ax + by = (a, b) ax+by=(a,b)的一组整数解，则 ∃ x , y ∈ Z \exists x, y \in \mathbb Z ∃x,y∈Z使贝祖等式 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,y∈Z使贝祖等式 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 ∴ax≡1(modp)=ax−py=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;
} 

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

这是不加任何优化的

扩欧

费马