Rockdu's Blog

题目背景

这是一道模板题

题目描述

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

输入输出格式

输入格式：

一行n,p

输出格式：

n行,第i行表示i在模p意义下的逆元。

输入输出样例

10 13

1
7
9
10
8
11
2
5
3
4

说明

1 \leq n \leq 3 \times 10 ^ 6, n < p < 200005281≤n≤3×10​6​​,n<p<20000528

输入保证 $p$ 为质数。

突然觉得之前太傻了……居然拿逆元硬转成了线性方程， 强行扩欧，时间复杂度爆棚。

其实我们推一下式子可以发现：求a mod b的逆元，a、b 在mod b下有以下性质：

1、a * 1 = a

2、a * 0 = mod

然后我们又发现，a和mod一定是互质的，因为如果不互质除运算时没有意义的。也就是说，如果对右边的式子做辗转相除，同时记录左边的数字，最后一定能得到a * m = 1 （在mod的意义下） ，就求出了逆元！

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int ext_gcd(int a, int b, int c, int d) {
	return d != 1 ? ext_gcd(b, a - (c / d) * b, d, c % d) : b;
}

int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	for(register int i = 1; i <= a; ++i) {
		int ans = ext_gcd(0, 1, b, i);
		if(ans < 0) ans = ans + ((0 - ans) / b + 1) * b;
		printf("%d\n", ans);
	}	
	return 0;
}

 但是其实可以线推的，看这篇博客：我是“这篇博客”。然后时间复杂度变成了O(n)

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 3e6 + 10;
int n, mod;
int inv[maxn];

int main() {
	inv[1] = 1;
	scanf("%d%d", &n, &mod);
	printf("1\n");
	for(register int i = 2; i <= n; ++i) {
		inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
		printf("%d\n", inv[i]);
	}
	return 0;
}