动态编程,时间复杂性问题



我需要在[A,B]中找到所有满足两个条件的间隔中的所有数字:

  • 可以被k
  • 排除
  • 数字的总和应在间隔[C,d]
  • 1≤k≤10^11;(1≤a,b< 10^11(;(1≤c,b≤99(

(1≤k≤10^11((1≤a,b< 10^11(

幼稚的实现(即使有改进(太慢。有人可以帮助实现它吗?也许是一些有用的建议&链接?我会感谢您的帮助。

我不认为动态编程可以在这里为您提供帮助。第一个条件非常简单地处理 - 您在[A,B]范围内迭代k。因此复杂性是O((B-A(/K(。至于第二个条件,您是否可以澄清一下中的" B"是否与第一个条件相同?如果是这样,那么利用它的结果是一个元素或一个空列表。因此复杂性是o(1(。如果" b"不同,我无法想象如何改善o((b-a(/k(利用第二条件。

最新更新