Python计算几何模板

暂时只是挖坑

一些模板

一般：

inv = pow(a, -1, m)

exgcd法:

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # 逆元不存在
    else:
        return x % m