LeetCode：1018. 可被 5 整除的二进制前缀

对我来说，这道题是位运算+同余原理应用的好题，直接用公式pow()硬算的话会导致耗时，并且nums元素很多时会直接溢出。参考答案给了一种耗时很小且不会溢出的解法。

1
2
//利用位运算和同余原理
prefix = ((prefix << 1) + nums[i]) % 5

首先是位运算，举{1, 0, 0, 1}为例，我们需要转换出{1, 10, 100, 1001}这四个二进制数字，可以直接用左移一位加上对应新一位的0或者1。

再论证一下同余原理的应用，已知ans[i]的prefix是一个余数，为什么直接对prefix进行位运算加上新一位再求模即是ans[i+1]的余数。m为5，下表c表示0或者1。

ans[] ans[i] ans[i+1]
余数 a % m (a * 2 + c) % m

由求余原理得

(a*2 + c) % m = (a%m * 2%m + c%m) % m

又因为

2 % m = 2，c % m = c

所以

(a*2 + c) % m = ((a%m) * 2) + c) % m

我们得到两个相邻余数之间的关系，prefix = (prefix*2 + c) % m得证。