数论基础一一同余定理
同余定理是数论中的重要概念，用于判断两数对同一模数的余数是否相同，记作 \(a \equiv b \ (\text{mod } m)\)。其核心性质包括加减性和乘性，广泛应用于优化前缀和相关问题。本文通过三道例题详细解析同余定理的应用：1）蓝“k倍区间”，利用哈希表记录余数出现次数，将时间复杂度从 \(O(n^2)\) 降至 \(O(n+k)\)；2）题“Subsequences Summing to Sevens S”，通过正序与倒序遍历寻找最长区间；3）AtCoder D题“Pedometer”，断环为链结合同余定理解决环形步数统计问题。这些实例展示了同余定理在算法竞赛中的高效应用。
