← 博客

Math

运算规则

  • //：向下取zheng
  • int(): 向0取整

质数

埃氏筛

比如想找到[2, right]中的所有质数

1
2
3
4
5
6
7
8
9

# 时间复杂度 O(right * log log right)

is_prime = [True]*(right+1)
is_prime[0]=is_prime[1]=False

for i in range(2, isqrt(right)+1):
    if is_prime[i]:
        for j in range(i * i, right+1 i):
            is_prime[j] = False

204. 计数质数

p[i]表示小于等于i的质数数量。从i=2开始，p[i]==0 <=> i是质数。则从ii开始，标记i的倍数为合数（通过令p[ik]=-1来实现）。并且，p[i]被赋值为p[i-1]+1

如果遇到p[i]<0，则i为合数，p[i]=p[i-1]

2523. 范围内最接近的两个质数

组合数学

乘法原理

快速幂

1922. 统计好数字的数目

注意python内置函数pow(x, y, m)用来计算x**y mod m

组合计数

2514. 统计同位异构字符串数目

用到了乘法逆元 Alt text a*pow(b,-1,m)%mod

convex hull

1
2
3
4
5

def det(x1: int, y1: int, x2: int, y2: int) -> int:
    return x1 * y2 - y1 * x2

result = det(B.x - A.x, B.y - A.y,    # 向量 AB
             C.x - B.x, C.y - B.y)    # 向量 BC

结果判断：

  • result > 0：C 在 AB 的左侧（逆时针转向）
  • result < 0：C 在 AB 的右侧（顺时针转向）
  • result = 0：A, B, C 共线

下凸包 凸包上相邻的三个点必须形成"左拐"（逆时针转向），不能"右拐"或"走直线"

从左往右、从下往上遍历所有点。建立一个栈，假设已经加入A, B

q=[A,B]

如果det(AB,BC)>0，则ABC是一个合理的下凸包

如果det(AB,BC)<=0，则弹出B，加入C

812. 最大三角形面积

首先建立凸包，然后通过同向双指针实现

暴力解法就是直接枚举所有面积

思维

逆向思维

780. 到达终点

逆向思维，每次用大的减小的

约瑟夫环

比如有这几个人：0 1 2 3 4
k=2
0杀掉1
然后把剩下的4个人重新标号，因为是从2开始杀人，所以变成
2(0),3(1),4(2),0(3)
括号内是新编号，括号外是旧编号
如果我们事先知道，有4个人，k=2时，胜利者为0
那即可得知：有5个人，k=2时，胜利者为2

1
2

f(n, k)=（ f(n-1, k)+k )%n
f(1,k)=0

最大公因数

任何非零整数 $a$ 与 $0$ 的最大公约数都是 $|a|$

1

g = gcd(*numsDivide)

python可以直接用gcd函数求一个数组的最大公因数

1
2
3
4

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return abs(a)

GCD 可以用来解决斜率精度问题（竖线）

149. 直线上最多的点数

为什么要用//?

因为用/的话，会出现-0.0和0.0这种情况

模

若 (A - B) % k = 0，则等价于 A % k = B % k

其它

2195. 向数组中追加 K 个整数

用求和公式