Частичная сумма

From

Vadim Lopatin (2:5015/149.13)

To

All

Date

2000-03-03T10:00:45Z

Area

RU.ALGORITHMS

Приветствую вас, уважаемый All!

Задача:

    Даны n натуральных чисел K1, K2, ..., Kn,
    n чисел M1, M2, ..., Mn,  M и B (все по заданному модулю N),
    M=M1*M2*M3*...*Mn

    Требуется найти все возможные комбинации A1, A2, ... An
    чтобы выполнялось равенство:

    A1*K1 + A2*K2 + ... + AnKn == B  (mod N)

    На Ai наложено ограничение:
        0 <= Ai <= Mi - 1

Существует ли эффективный алгоритм ее решения, можно для частных случаев:
a) M=N  (или M порядка N)
b) M=sqrt(N)  ( или M порядка sqrt(N) )
c) n=2

Как влияют на решения выбор Ki?
Что, если Ki простые или попарно взаимно простые (или наоборот, имеют много
общих делителей)?
Что лучше, уменьшить n, увеличив Mi или уменьшить Mi за счет увеличения n?


Может быть, известно эффективное решение (или доказано отсутствие такового)
для похожей задачи?

Конечно, данную задачу легко свести к проблеме частичной суммы, которая
является NP-полной (NP-трудной?). Но данный частный случай имхо должен сильно
упростить решение.

З.Ы.: Можно легко выбирать M, N, n, Mi. Ki и B зависят от других параметров.

С уважением, Vadim

--- Graphoman Toolkit 3.00
 * Origin: LazyBeing station (2:5015/149.13)