逆元

如果 \(gcd(a,m) = 1\) 且存在唯一的 \(b\) 存在 \(a \times b \equiv 1 \pmod m\) 且 \(1\leq b<m\), \(b\) 为 \(a\) 在模 \(m\) 意义下的逆元

费马小定理 \(a ^ {p - 1}\equiv 1\pmod p (gcd(a, p) = 1)\)
欧拉定理 \(a ^ {\phi(m)} \equiv 1 \pmod m (gcd(a, m) = 1)\)
扩展欧拉定理

• \(c < \phi(m)\) 则 \(a^c\equiv a^c \pmod m\)
• \(c \ge \phi(m)\) 则 \(a^c\equiv a^{[c \bmod \phi(m)] + \phi(m)} \pmod m\)

线性求逆元
\(a ^ {p - 1}\equiv 1\pmod p (gcd(a, p) = 1)\)
\(m \bmod a = m - a \times \lfloor \frac{m}{a} \rfloor\)
设 \(b = m \bmod a\)
\(a^{-1}\equiv a^{-1} \times b\times b^{-1} = a^{-1}\times (m - a \times \lfloor \frac{m}{a} \rfloor)\times b^{-1} \pmod m\)
得 \(a^{-1}\equiv -\lfloor \frac{m}{a} \rfloor \times b^{-1} \pmod m\)

原根

定义 : 在模 \(m\) 的意义下, 算出 \(a^1, a^2, a^3 ... a^{\phi(m)}\), 如果这些数两两互不相等, 则 \(a\) 为模 \(m\) 意义下的原根
给定一个 \(m\) 找到一个在模 \(m\) 意义下的原根 \(a\) : 发现一个数 \(m\) 为原根只可能是 \(2, 4, p^a, 2p^a\) , 又发现原根 \(a\) 一定 \(\leq 10\), 于是可以暴力判断check
优化 check的时候发现对于 \(a^i = a^j (i < j)\) 必定会存在 \(a^k = 1 (k = j - i)\), 发现 \(k\) 只可能是 \(k | \phi(m)\) (可以用欧拉定理和循环节考虑), 于是可以 \(\sqrt m\) 求解

bool check(int m, int a) {
	int phi = get_phi(m);
	for (int i = 2; i <= sqrt(phi); i++) {
		if (phi % i == 0) {
			if (ksm(a, i, m) == 1) return false;
			if (ksm(a, m / i, m) == 1) return false;
		}
	}
	return true;
} 

int get_yg(int m) {
	for (int i = 1; i; i++) {
		if (check(m, i)) return i;
	}
}

Miller_Rabin素性测试

常规判定素数方法： 从 \(1至\sqrt{n}\) 中枚举 \(p\) ，判断 \(p | n\)

Miller_Rabin
对于一个 \(n\) ,假如它是质数
设 \(n - 1 = d \times 2^r\) , 其中 \(d\) 是一个奇数
对于每一个 \(1 \leq a < n\) 对于下面两种条件,至少有一个是成立的

• \(a^d \equiv 1 \pmod n\)
• 存在 \(0 \leq i < r\) , 满足 \(a^{d\times2^i}\equiv n-1\pmod n\)

于是当前对于 \(1 \leq a<n\)

• 满足至少一个条件 --> \(n\) 可能是质数
• 两个条件都不满足 --> \(n\) 一定不是质数

于是可以寻找对个 \(a\) 对 \(n\) 进行检测, 如果全部通过检测有极大概率 \(n\) 为质数

bool miller_rabin(int n, int a) {
	int d = n - 1, r = 0;
	while (!(d & 1)) 
		d >>= 1, r++;
	int x = ksm(a, d, n);
	if (x == 1) return true;
	for (int i = 0; i < r; i++) {
		if (x == n - 1) return true;
		x = 1ll * x * x % n;
	}
	return false;
} 

bool prime(int n) {
	if (n < 2) return false;
	int prime_list[10] = {2, 3, 5, 11, 17, 19, 23, 37, 41, 43};
	for (int a = 0; a < 10; a++) {
		if (n == prime_list[a]) return true;
		if (!miller_rabin(n, prime_list[a])) return false;
	}
	return true;
}