裴蜀（贝祖）定理
ax+by=c gcd(a,b)|c a,b 已知且为正整数ax+by(min)=gcd(a,b)
inv[a]≡a^-1(%m)则inv[a]为a%m 的逆元
求法 当m 为质数inv[a]=a^(m-2)
要求 a/b%m=ab^-1%m=ainv[b]%m
* 欧拉定理
对于互质的a 和n 有a^φ(n)%n=1
欧拉函数φ(n)=小于等于n 的正整数中与n 互质的数的个数
欧拉函数求法
φ(1)=1
φ(p)=p-1
φ(p^k)=p^k-p^(k-1)=
若n=ab a,b 互质 则φ(n)=φ(a)φ(b) (积性函数)
n=p1^k1p2^k2…… φ(n)=n(p1-1)/p1*(p2-1)/p2……
卢卡斯定理
通常先预处理出C[a][b](a,b
然后再次使用卢卡斯进行计算
Original: https://www.cnblogs.com/29taorz/p/15304179.html
Author: T_X蒻
Title: 一些数学
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584347/
转载文章受原作者版权保护。转载请注明原作者出处！