费马小定理

常用在gcd,最大公因数中

  • 费马小定理(Fermat’s little theorem)是数论中的一个重要定理,在1636年提出。如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。 [1]

向上取整公式

一般语言的math自带ceil,但是我们可以避免浮点数运算,因为浮点数有误差

1
ceil(a / b) = (a + b - 1) / b