Блог пользователя codeedoc

Hi! I need a little help with a problem .
Автор codeedoc, 5 лет назад, По-английски

this should be a classical problem: We have a group of numbers named A with the size of n. Does A have a subgroup such that the sum of it is divisible by m?
m,n>=10^5

I couldn't find any solution with an order better than O(n*m).

thanks for helping :)

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There is a randomized tilde-O(n+m) solution for prime m out there, but I'm not sure if it's feasible with your constraints since its constants are fairly high. I'm pretty sure there's a way to adapt the solution to non-prime m, though I haven't spent too much time trying to do so.

→ Ответить