数论
大约 7 分钟
数论
素数（筛）
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 质数/素数
*/
public class Prime {
/**
* 判断 num 是否是质数
* 时间复杂度 O(√n)
*/
private static boolean isPrime(long num) {
if (num < 2) {
return false;
}
for (long i = 2; i * i <= num; ++i) {
if (num % i == 0) {
return false;
}
}
return true;
}
/**
* 埃氏筛
* 时间复杂度 O(nloglogn)
* 空间复杂度 O(n)
*/
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
int cnt = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
cnt++;
if (i * i < n) {
for (int j = i; j < n; j += i) {
isPrime[j] = false;
}
}
}
}
return cnt;
}
/**
* 线性筛
* 时间复杂度 O(n)
* 空间复杂度 O(n)
*/
public int countPrimes2(int n) {
List<Integer> primes = new ArrayList<>();
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
primes.add(i);
}
for (int j = 0; j < primes.size() && i * primes.get(j) < n; j++) {
isPrime[i * primes.get(j)] = false;
if (i % primes.get(j) == 0) {
break;
}
}
}
return primes.size();
}
}
Miller–Rabin 素性测试
Miller–Rabin 素性测试（Miller–Rabin primality test）是进阶的素数判定方法。它是由 Miller 和 Rabin 二人根据费马小定理的逆定理（费马测试）优化得到的。因为和许多类似算法一样，它是使用伪素数的概率性测试，我们必须使用慢得多的确定性算法来保证素性。然而，实际上没有已知的数字通过了高级概率性测试（例如 Miller–Rabin）但实际上却是合数。因此我们可以放心使用。
boolean Miller_Rabin(long p) { // 判断素数
if (p < 2) return false;
if (p == 2) return true;
if (p == 3) return true;
long d = p - 1, r = 0;
while ((d & 1) == 0) {
++r;
d >>= 1;
} // 将d处理为奇数
for (long k = 0; k < 10; ++k) {
long a = rand() % (p - 2) + 2;
long x = quickPow(a, d, p);
if (x == 1 || x == p - 1) continue;
for (int i = 0; i < r - 1; ++i) {
x = cheng(x, x, p);
if (x == p - 1) break;
}
if (x != p - 1) return false;
}
return true;
}
最大公约数
欧几里得算法。
时间复杂度：O(n)。
private static int getGCD(int num1, int num2) {
if (num1 == 0) {
return num2;
}
return getGCD(num2 % num1, num1);
}
乘法逆元
| 题目 | 难度 | |
|---|---|---|
| 1916. 统计为蚁群构筑房间的不同顺序 | 困难 | T4 线性求逆元 |
| 2400. 恰好移动 k 步到达某一位置的方法数目 | 困难 | T2 组合数学 |
| 2438. 二的幂数组中查询范围内的乘积 | 中等 | T2 |
| 2514. 统计同位异构字符串数目 | 中等 | T4 |
| DD-2019011. DIST | 简单 | |
| abc280_e |
exgcd 求逆元：
import java.nio.charset.StandardCharsets;
import java.util.Scanner;
public class Abc280_e {
private static final int MOD = 998244353;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8);
int n = scanner.nextInt();
int p = scanner.nextInt();
System.out.println(solve(n, p));
}
private static String solve(int n, int p) {
// x = 1 - x*p/100
// ans += x
long inv = inv(100, MOD);
long x = 1, ans = 1;
for (int i = 0; i < n - 1; i++) {
x = (1 - x * p % MOD * inv % MOD + MOD) % MOD;
ans = (ans + x) % MOD;
}
return String.valueOf(ans);
}
static long inv(long a, long b) {
x = 0;
y = 0;
exgcd(a, b);
return (x + b) % b;
}
static long x, y;
static long exgcd(long a, long b) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long d = exgcd(b, a % b);
long tmp = x;
x = y;
y = tmp - a / b * y;
return d;
}
}
1916. 统计为蚁群构筑房间的不同顺序
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Solution1916 {
private static final int MOD = (int) (1e9 + 7);
private Map<Integer, List<Integer>> adj;
private long[] fac;
private long[] inv;
private long[] f;
private int[] cnt;
// 时间复杂度 O(nlogn)
public int waysToBuildRooms(int[] prevRoom) {
int n = prevRoom.length;
adj = new HashMap<>();
for (int i = 1; i < n; i++) {
adj.computeIfAbsent(prevRoom[i], key -> new ArrayList<>()).add(i);
}
// fac[i] 表示 i!
// inv[i] 表示 i! 的乘法逆元
fac = new long[n];
inv = new long[n];
fac[0] = 1;
inv[0] = 1;
for (int i = 1; i < n; ++i) {
fac[i] = fac[i - 1] * i % MOD;
// 使用费马小定理计算乘法逆元
inv[i] = quickPow(fac[i], MOD - 2);
}
f = new long[n];
cnt = new int[n];
dfs(0);
return (int) f[0];
}
private void dfs(int u) {
f[u] = 1;
for (int v : adj.getOrDefault(u, new ArrayList<>())) {
dfs(v);
// 乘以左侧的 f[ch] 以及右侧分母中 cnt[ch] 的乘法逆元
f[u] = f[u] * f[v] % MOD * inv[cnt[v]] % MOD;
cnt[u] += cnt[v];
}
// 乘以右侧分子中的 (cnt[i] - 1)!
f[u] = f[u] * fac[cnt[u]] % MOD;
cnt[u]++;
}
// 模下的 a^b
private long quickPow(long a, long b) {
long res = 1L;
while (b > 0) {
if ((b & 1) == 1) {
res = res * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return res;
}
// 线性求逆元 https://oi-wiki.org/math/number-theory/inverse/#%E7%BA%BF%E6%80%A7%E6%B1%82%E9%80%86%E5%85%83
// 时间复杂度 O(n + logp)
public int waysToBuildRooms2(int[] prevRoom) {
int n = prevRoom.length;
adj = new HashMap<>();
for (int i = 1; i < n; i++) {
adj.computeIfAbsent(prevRoom[i], key -> new ArrayList<>()).add(i);
}
// fac[i] 表示 i!
fac = new long[n];
fac[0] = 1;
for (int i = 1; i < n; ++i) {
fac[i] = fac[i - 1] * i % MOD;
}
// 线性求逆元
// 前缀积
long[] s = new long[n + 1];
// 前缀积逆元
long[] sv = new long[n + 1];
s[0] = 1;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] * fac[i - 1] % MOD;
}
sv[n] = quickPow(s[n], MOD - 2);
// 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
for (int i = n; i >= 1; --i) {
sv[i - 1] = sv[i] * fac[i - 1] % MOD;
}
// inv[i] 表示 i! 的乘法逆元
inv = new long[n];
for (int i = 1; i <= n; ++i) {
inv[i - 1] = sv[i] * s[i - 1] % MOD;
}
f = new long[n];
cnt = new int[n];
dfs(0);
return (int) f[0];
}
}
2400. 恰好移动 k 步到达某一位置的方法数目
public class Solution2400 {
private static final long MOD = (long) (1e9 + 7);
// 乘法逆元 时间复杂度 O(k)
public int numberOfWays(int startPos, int endPos, int k) {
int diff = Math.abs(startPos - endPos);
if ((k - diff) % 2 != 0 || diff > k) {
return 0;
}
// 总 k 步
// 向左 (k-diff)/2 向右 k - (k-diff)/2
// C(k, (k-diff)/2)
return (int) combination(k, (k - diff) / 2, (int) MOD);
}
// C(n, m) = n! / m!(n-m)! （n 为下标） (% mod)
private long combination(int n, int m, int mod) {
// 线性求逆元
long[] inv = new long[n + 1];
inv[1] = 1;
for (int i = 2; i <= n; i++) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
// 递推求组合数，初值 C(k, 0) = 1
long res = 1;
for (int i = 1; i <= m; i++) {
res = res * (n - i + 1) % mod * inv[i] % mod;
}
return res;
}
}
分解质因数
import java.util.ArrayList;
import java.util.List;
/**
* 分解质因数
* https://oi-wiki.org/math/number-theory/pollard-rho/
* CF1744E1
* Abc280_d
*/
public class Factor {
/**
* 分解质因数
*/
private static List<Long> getFactorPrime(long num) {
List<Long> resList = new ArrayList<>();
for (long i = 2; i * i <= num; i++) {
// 如果 i 能够整除 N，说明 i 为 N 的一个质因子。
if (num % i == 0) {
while (num % i == 0) {
num /= i;
}
resList.add(i);
}
}
// 说明再经过操作之后 N 留下了一个素数
if (num != 1) {
resList.add(num);
}
return resList;
}
/**
* 因数
* https://oeis.org/A066150
*/
private static List<Long> getFactors(long num) {
List<Long> factors = new ArrayList<>();
for (long i = 1; i * i <= num; i++) {
if (num % i == 0) {
factors.add(i);
factors.add(num / i);
}
}
return factors;
}
}
Pollard Rho 算法
| 题目 | 难度 | |
|---|---|---|
| LQ240323T7 赛博奴隶主【算法赛】 |
long Pollard_Rho(long x) {
long s = 0, t = 0;
long c = rand() % (x - 1) + 1;
int step = 0, goal = 1;
long val = 1;
for (goal = 1; ; goal *= 2, s = t, val = 1) { // 倍增优化
for (step = 1; step <= goal; ++step) {
t = (cheng(t, t, x) + c) % x;
val = cheng(val, Math.abs(t - s), x);
if ((step % 127) == 0) {
long d = getGCD(val, x);
if (d > 1) return d;
}
}
long d = getGCD(val, x);
if (d > 1) return d;
}
}
裴蜀定理
设 a, b 是不全为零的整数，则存在整数 x, y，使得 ax + by = gcd(a, b)。
| 题目 | 难度 | |
|---|---|---|
| 365. 水壶问题 | 中等 | 裴蜀定理 |
| 1250. 检查「好数组」 | 困难 | 裴蜀定理 |
365. 水壶问题
public class Solution365 {
public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
if (jug1Capacity + jug2Capacity < targetCapacity) {
return false;
}
if (jug1Capacity == 0 || jug2Capacity == 0) {
return targetCapacity == 0 || jug1Capacity + jug2Capacity == targetCapacity;
}
return targetCapacity % getGCD(jug1Capacity, jug2Capacity) == 0;
}
private int getGCD(int num1, int num2) {
if (num1 == 0) {
return num2;
}
return getGCD(num2 % num1, num1);
}
}
1250. 检查「好数组」
public class Solution1250 {
public boolean isGoodArray(int[] nums) {
// 裴蜀定理
int gcd = nums[0];
for (int i = 1; i < nums.length; i++) {
gcd = getGCD(gcd, nums[i]);
if (gcd == 1) {
break;
}
}
return gcd == 1;
}
private int getGCD(int num1, int num2) {
if (num1 == 0) {
return num2;
}
return getGCD(num2 % num1, num1);
}
}
（全文完）