费马小定理

同余定理，也称为费马小定理（Fermat’s Little Theorem）或费马同余定理，在数论中是一个非常重要的概念。然而，同余定理这个术语可能引起一些混淆，因为它既可以指代费马小定理，也可以泛指数学中的同余概念及其相关定理。这里，我将分别解释同余概念和费马小定理。

同余概念#

同余是数论中的一个基本概念，由高斯引入。如果两个整数$a$和$b$除以正整数$m$（称为模）得到的余数相等，那么就说$a$和$b$对模$m$同余，记作$a \equiv b \pmod{m}$。

同余理论中的一些基本性质包括：

• 如果$a \equiv b \pmod{m}$且$c \equiv d \pmod{m}$，那么$a+c \equiv b+d \pmod{m}$和$ac \equiv bd \pmod{m}$。
• 如果$a \equiv b \pmod{m}$，那么对任意整数$k$，有$ka \equiv kb \pmod{m}$。

费马小定理#

费马小定理是同余理论中的一个特殊情况，它描述了素数与整数幂之间的一种特殊关系。费马小定理说：

如果$p$是一个素数，且$a$是任意一个不被$p$整除的整数，则$a^{p-1} \equiv 1 \pmod{p}$。

换句话说，$a$的$p-1$次幂减去$1$能被$p$整除。

费马小定理有一个常见的推广形式，如果$p$是素数，则对任何整数$a$，有$a^p \equiv a \pmod{p}$。

应用#

同余理论和费马小定理在密码学、编码理论、算法设计以及数学证明中都有广泛的应用。例如，费马小定理是RSA加密算法中重要组成部分之一。

综上所述，同余概念提供了一种判断整数除以某个数的余数是否相等的方法，而费马小定理是这个概念在素数和整数幂上的一个特殊应用。

例题 16.k倍区间 - 蓝桥云课 (lanqiao.cn)#

题目大意：

题目要我们找区间，所以无脑使用前缀和数组sum[]预处理输入。

如果枚举所有区间和，即便使用了前缀和，时间复杂度可以到$O(N^2)$，依然会有几个样例超时。

回忆一下同余定理，题目让我们寻找k倍区间，即$(sum[r]−sum[l−1])mod k = 0$，移项可得$sum[r]modk=sum[l−1]modk$，换句话说就是让我们找有多少个前缀和$sum[i]$模$k$后相等，比如模$k$后相等的$sum[i]$有$n$个，那么从中任取两个代入前面的公式都可以找出一个k倍区间。

同时对于任意 $sum[i]modk$ 其结果只可能是 0 ~ k-1，因此可以用一个数组记录 $sum[i]modk$ 相等的个数，由组合数 $C_{n}^{2}(0 <= n <= k-1)$可以求出模相等的前缀和可以得到几个 k 倍区间，这样，我们遍历数组就可以得到答案