逆元模板、求1~n每个数的逆元模板

• 欧拉定理：若 a a a 和 n n n 互质，则 a φ ( n ) ≡ 1     ( m o d    n ) a^{\varphi(n)}\equiv1\space\space\space(mod\space\space n) aφ(n)≡1   (mod  n)

• 欧拉定理的推论（费马定理）：在 a a a 和 p p p 互质的前提下，当 p p p 为质数时， a p − 1 ≡ 1     ( m o d    p ) a^{p-1}\equiv1\space\space\space(mod\space\space p) ap−1≡1   (mod  p)

• 乘法逆元定义：若整数 b b b、 m m m 互质，并且 b ∣ a b|a b∣a，则存在一个整数 x x x，使得 a / b ≡ a ∗ x    ( m o d    m ) a/b\equiv a*x\space\space (mod\space\space m) a/b≡a∗x  (mod  m)，称 x x x 为 b b b 的模 m m m 乘法逆元，记为 b − 1 ( m o d    m ) b^{-1} (mod\space\space m) b−1(mod  m)。

  b b b 存在乘法逆元的充要条件是 b b b 与模数 m m m 互质。当模数 m m m 为质数时， b m − 2 b^{m-2} bm−2 即为 b b b 的乘法逆元。

问题转换为快速幂的计算： 快速幂模板

逆元模板

#include
using namespace std;

typedef long long LL;

LL ksm (LL a, LL k, LL p) {
	LL res = 1;
	while (k) {
		if (k & 1) res = res * a % p;
		a = a * a % p;
		k >>= 1;
	}
	return res;
}

int main()
{
	LL n, p;
	cin >> n >> p;
	
	cout