c++ - 如何在 C++ 中有效地找到具有给定余数的产品？

Question

如果我得到一个像 23,128,765 这样的数字，并且又得到两个数字 9 和 3，我想计算对的数量，使得对于 9 和 3，除以 9 后余数为 3 的子串是:3， 31,287、12 和 876。

如何使用 C++ 计算此类子串的数量？

一种可能的方法是计算所有可能的子字符串，但那是 O(n^2)，但我想要比这更快的东西。

Answer 1

您要求使用 C++，但这是 Common Lisp 中的解决方案，在这种情况下更容易编写和演示:

(defun quotients-with-remainder-in (n divisor remainder)
  (loop with str = (format nil "~D" n)
        for i upfrom remainder to n by divisor
        when (search (format nil "~D" i) str)
          collect i))

> (quotients-with-remainder-in 23128765 9 3)
(3 12 876 31287)

除数向上迈进，并将每个潜在产品转换为字符串，并在上限数字的字符串表示中搜索该字符串。

一路上创建了许多字符串，但是找到一种方法来操作整数以查看一个整数的十进制表示是否出现在另一个整数的十进制表示中，这不适用于任何算术运算。例如，判断数字 131 是否“包含”一个 3 不能通过算术和检查二进制补码表示来完成。

好吧，让我们看看；也许你可以将候选数乘以 10 的因数，并且对于每个这样的产品从原始数字中减去它，然后检查差异中的重要数字是否全部为零，为此你可以使用模运算符对幂10 乘积的以 10 为底的对数大一。我开始编写这样的解决方案，但它很快就偏离了轨道。使用额外的对数、乘法和除法可能会产生比字符串转换和子字符串搜索更慢的解决方案。