费马小定理
同余定理,也称为费马小定理(Fermat’s Little Theorem)或费马同余定理,在数论中是一个非常重要的概念。然而,同余定理这个术语可能引起一些混淆,因为它既可以指代费马小定理,也可以泛指数学中的同余概念及其相关定理。这里,我将分别解释同余概念和费马小定理。
同余概念
同余是数论中的一个基本概念,由高斯引入。如果两个整数和除以正整数(称为模)得到的余数相等,那么就说和对模同余,记作。
同余理论中的一些基本性质包括:
- 如果且,那么和。
- 如果,那么对任意整数,有。
费马小定理
费马小定理是同余理论中的一个特殊情况,它描述了素数与整数幂之间的一种特殊关系。费马小定理说:
如果是一个素数,且是任意一个不被整除的整数,则。
换句话说,的次幂减去能被整除。
费马小定理有一个常见的推广形式,如果是素数,则对任何整数,有。
应用
同余理论和费马小定理在密码学、编码理论、算法设计以及数学证明中都有广泛的应用。例如,费马小定理是RSA加密算法中重要组成部分之一。
综上所述,同余概念提供了一种判断整数除以某个数的余数是否相等的方法,而费马小定理是这个概念在素数和整数幂上的一个特殊应用。
例题 16.k倍区间 - 蓝桥云课 (lanqiao.cn)
题目大意:
题目要我们找区间,所以无脑使用前缀和数组sum[]
预处理输入。
如果枚举所有区间和,即便使用了前缀和,时间复杂度可以到,依然会有几个样例超时。
回忆一下同余定理,题目让我们寻找k倍区间,即,移项可得,换句话说就是让我们找有多少个前缀和模后相等,比如模后相等的有个,那么从中任取两个代入前面的公式都可以找出一个k倍区间。
同时对于任意 其结果只可能是 0 ~ k-1
,因此可以用一个数组记录 相等的个数,由组合数 可以求出模相等的前缀和可以得到几个 k
倍区间,这样,我们遍历数组就可以得到答案