如何求能被7整除的数字个数？

给定一个整数N，如何有效地找到范围内能被 7 整除的数字的个数（其逆序也能被 7 整除）：

• [0, 10^N - 1]

Example:

For N=2， 回答：

• 4 {0, 7, 70, 77}

[0到99之间所有能被7整除的数字（它们的倒数也能被7整除）]

我的方法，简单的暴力：

• 将计数初始化为零
• 运行一个循环i=0直到结束
• if a(i) % 7 == 0 && reverse(a(i)) % 7 == 0，然后我们增加计数

Note:

• reverse(123) = 321, reverse(1200) = 21， 例如！

让我们看看当我们添加一个数字时 mod 7 会发生什么，d, 到前缀,abc.

10 * abc + d =>
  (10 mod 7 * abc mod 7) mod 7 + d mod 7

reversed number:

abc + d * 10^(length(prefix) =>
  abc mod 7 + (d mod 7 * 10^3 mod 7) mod 7

注意，我们只需要前缀的数量abc mod 7对于每个这样的余数，而不是实际的前缀。