如何求可被7整除的数的计数？

Question

给定一个整数n，如何有效地找到范围内可被7整除的数的计数（它们的反向也应可被7整除）：

null

对于n=2，请回答：

• 4{0,7,70,77}

[从0到99的所有可被7整除的数（它们的反向也可整除）]

null

null

Answer 1

让我们看看当我们在前缀abc中添加一个数字d时会发生什么。

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 mod7的前缀计数，而不是实际的前缀。