6.1 初级
（1）模运算
- Java计算规则：先按正整数求余，然后加上符号，符号与被除数保持一致
- Python计算规则：向下对齐 \(123\;//\;(-10)=-13\)，故 \(123\;\%\;(-10)=123-(-10)\times(-13)=-7\)
def fastMul(num1: int, num2: int, mod: int) -> int:
"""使用快速乘法 返回 num1 * num2 % mod 的结果"""
num1 %= mod; num2 %= mod; res = 0
while num2 > 0:
if num2 & 1:
res = (res + num1) % mod
num1 = (num1 + num1) % mod
num2 >>= 1
return res
（2）快速幂
def fastPow(a: int, n: int, mod: int) -> int:
"""使用快速幂计算 a ^ n % mod 的结果"""
a %= mod; res = 1
while n > 0:
if n & 1:
res = (res * a) % mod
a = (a * a) % mod
n >>= 1
return res
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long T = sc.nextLong(), N, M, P;
for(int i = 0; i < T; i++) {
N = sc.nextLong();
M = sc.nextLong();
P = sc.nextLong();
System.out.println(fastPow(N, M, P));
}
sc.close();
}
static long fastPow(long n, long m, long p) {
n %= p; long ans = 1;
while(m > 0) {
if((m & 1) == 1)
ans = ans * n % p;
n = n * n % p;
m >>= 1;
}
return ans;
}
}
（3）高斯消元
import java.util.Scanner;
public class Main {
static double eps = 1e-7;
static double temp; // 临时变量
static boolean flag = true;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
double[][] a = new double[105][105];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n + 1; j++)
a[i][j] = sc.nextInt();
}
for(int i = 1; i <= n && flag; i++) { // 枚举每一列
int idx = i; // 记录最大系数的行标
for(int j = i + 1; j <= n; j++) {
if(Math.abs(a[j][i]) > Math.abs(a[idx][i]))
idx = j;
}
for(int j = i; j <= n + 1; j++) { // 交换两行
temp = a[i][j]; a[i][j] = a[idx][j]; a[idx][j] = temp;
}
if(Math.abs(a[i][i]) < eps) {
System.out.println("No Solution");
flag = false; break;
}
for(int j = n + 1; j >= i; j--) // 系数变为1
a[i][j] /= a[i][i];
for(int j = 1; j <= n; j++) { // 消去其他行的主元
if(j == i) continue;
temp = a[j][i] / a[i][i];
for(int k = i; k <= n + 1; k++) {
a[j][k] -= a[i][k] * temp;
}
}
}
for(int i = 1; i <= n && flag; i++) {
System.out.println(String.format("%.2f", a[i][n + 1]));
}
}
}
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
eps = 1e-7 # 定义精度
flag = True
for i in range(n): # 枚举每一列
idx = i # 记录第 i 列最大系数所在行数
for j in range(i + 1, n):
if abs(a[j][i]) > abs(a[idx][i]):
idx = j
# 交换第 i 行和第 idx 行
for j in range(i, n + 1):
a[i][j], a[idx][j] = a[idx][j], a[i][j]
if abs(a[i][i]) < eps:
print("No Solution") # 无解
flag = False; break
if not flag:
break
for j in range(n, i - 1, -1): # 将系数变为 1
a[i][j] /= a[i][i]
for j in range(n): # 消去主元所在的其他行
if i == j: continue
temp = a[j][i] / a[i][i]
for k in range(i, n + 1):
a[j][k] -= a[i][k] * temp
if flag:
for i in range(n):
print("{:.2f}".format(a[i][n]))
（4）GCD和LCM
import java.util.Scanner;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BigInteger a = sc.nextBigInteger();
BigInteger b = sc.nextBigInteger();
System.out.println(a.gcd(b));
}
}
- 裴蜀定理 \(ax+by=gcd(a,b)\)
（5）素数（质数）
⭐ 判定
1 试除法
from math import isqrt
def isPrime(num: int) -> bool:
if num <= 1: return False
for i in range(2, isqrt(num) + 1):
if num % i == 0:
return False
return True
2 Miller-Rabin算法
from random import randint
def witness(a: int, n: int) -> bool:
# 计算 u 和 t
u, t = n - 1, 0
while u & 1 == 0:
u >>= 1; t += 1
x1 = pow(a, u, n) # 进行二次探测
for i in range(t):
x2 = pow(x1, 2, n)
if x2 == 1 and x1 != 1 and x1 != n - 1:
return True # 二次探测定理
x1 = x2
return x1 != 1 # 费马小定理
def millerRabin(n: int, k: int) -> bool:
"""判定 n 是否为素数"""
if n == 2: return True
if n <= 1 or n % 2 == 0: return False
for i in range(min(n, k)): # 进行测试
# 返回一个 [2, n - 1] 之间的随机整数
a = randint(2, n - 1)
if witness(a, n):
return False
return True
import java.util.Scanner;
import java.math.BigInteger;
public class Test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), cnt = 0;
BigInteger a;
for(int i = 0; i < N; i++) {
a = sc.nextBigInteger();
cnt += a.isProbablePrime(1) ? 1 : 0;
}
System.out.println(cnt);
}
}
⭐ 筛选
1 埃式筛
from math import isqrt
def eSieve(n: int) -> list[int]:
prime, vis = list(), [True] * (n + 1)
vis[0] = vis[1] = False # 0 1 不是素数
for i in range(2, isqrt(n) + 1): # 优化 1
if vis[i]: # 当前数是素数
for j in range(i * i, n + 1, i): # 优化 2
vis[j] = False # 标记合数
for i in range(2, n + 1):
if vis[i]: prime.append(i) # 收集素数
return prime
2 欧拉筛
def eulerSieve(n: int) -> list[int]:
prime, vis = list(), [True] * (n + 1)
vis[0] = vis[1] = False # 0 1 不是素数
for i in range(2, n + 1):
if vis[i]: # 当前数是素数
prime.append(i)
for j in prime: # 用得到的素数去筛后面的数
if j * i > n: break # 超出范围
vis[j * i] = False
if i % j == 0: break # 避免重复筛
return prime
⭐ 质因数分解
1 最小质因数（欧拉筛）
def eulerSieve(n: int) -> list[int]:
# prime 记录素数 vis 记录每个数的最小质因数
prime, vis = list(), [0] * (n + 1)
for i in range(2, n + 1):
if vis[i] == 0: # 当前数是素数
vis[i] = i; prime.append(i)
for j in prime: # 对于已经找到的素数
if j * i > n: break
vis[j * i] = j
if i % j == 0: break
return vis
2 试除法
from math import isqrt
def factor(n: int) -> list[tuple]:
p = list() # 记录质因子和指数
for i in range(2, isqrt(n) + 1):
cnt = 0 # 记录指数
while n % i == 0:
cnt += 1; n //= i
if cnt: # 记录质因子和指数
p.append((i, cnt))
if n > 1: # 没有除尽是素数
p.append((n, 1))
return p
3 pollard_rho启发式方法
from random import randint
from math import gcd
def witness(a: int, n: int) -> bool:
# 计算 u 和 t
u, t = n - 1, 0
while u & 1 == 0:
u >>= 1; t += 1
x1 = pow(a, u, n) # 进行二次探测
for i in range(t):
x2 = pow(x1, 2, n)
if x2 == 1 and x1 != 1 and x1 != n - 1:
return True # 二次探测定理
x1 = x2
return x1 != 1 # 费马小定理
def millerRabin(n: int, k: int) -> bool:
"""判定 n 是否为素数"""
if n == 2: return True
if n <= 1 or n % 2 == 0: return False
for i in range(min(n, k)): # 进行测试
# 返回一个 [2, n - 1] 之间的随机整数
a = randint(2, n - 1)
if witness(a, n):
return False
return True
def pollardRho(n: int) -> int:
i, k = 1, 2 # 记录 x 和 y 对应的下标
# 初始化 c[1, n - 1] x[0, n - 1] y
c, x = randint(1, n - 1), randint(0, n - 1)
y = x
while True: # 寻找因数
x = ((x * x) % n + c) % n # x * x 可能溢出使用快速乘
i += 1 # x 进行了更新
d = gcd(abs(x - y), n) # 计算最大公约数
if d != 1 and d != n: # 找到因数
return d
if y == x: return n # 回路
if i == k: # 更新 y
y = x; k <<= 1
def findfac(n: int) -> None:
# 寻找 n 的所有质因子
if millerRabin(n, 50): # 是质因数
factor[n] = factor.get(n, 0) + 1
return
p = n
while p >= n: # 找到一个因数
p = pollardRho(p)
findfac(p) # 寻找质因数
findfac(n // p) # 寻找质因数