Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$

I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \ldots, b_D)$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ is a multiple of $c$.

The brute force search I came up with is

• Let $t$ be the smallest multiple of $c$ that is $\ge \prod_{i = 1}^{D} a_i$.

• Use depth-first-search to search for values $\hat{b}$, starting at $\mathbf{0}$ and incrementing one element of $\hat{b}$ at a time until $\prod_{i = 1}^{D} \left(a_i + \hat{b}_i\right) \geq t$.

• If we found $\hat{b}$ such that $\prod_{i = 1}^{D} \left(a_i + \hat{b}_i\right) = t$ then $\hat{b}$ is the optimal solution. Otherwise increment $t$ by $c$ and go back to step 2.

The above algorithm does work, but if $D$ or $c$ are too large then it will potentially take a very very long time. I'm wondering if this maps to any well known algorithm or if there's a more efficient solution. I'm considering that the prime factors of $c$ and $a$ could play a large role in reducing the search space but I can't quite figure it out.

In case anyone wants to play with this, a Python 3 implementation of the brute force algorithm described above is
`from functools import reduce
from operator import mul

def prod(x):
return reduce(mul, x, 1)

def ceil_divide(num, denom):
return -(-num // denom)

def update_memory(b, memory):
tuple_b = tuple(b)
if tuple_b in memory:
return False
memory.add(tuple_b)
return True

def dfs(a, b, t, memory):
if not update_memory(b, memory):
return False

p = prod([ai + bi for ai, bi in zip(a, b)])
if p == t:
return True
elif p > t:
return False

for i in range(len(a)):
b[i] += 1
if dfs(a, b, t, memory):
return True
b[i] -= 1

def solve(a, c):
b = [0 for _ in range(len(a))]
t = c *

If $c$ doesn't have too many factors and is not too large, the following should work reasonably well for typical numbers.

Factor $c$ into its prime factorization, say $c=p_1^{e_1} \cdots p_k^{e_k}$. Enumerate all tuples $(f_1,\dots,f_D)$ of non-negative integers such that $f_1 \cdots f_D = c$. For each such tuple $(f_1,\dots,f_D)$, and each $i$, find the smallest $b_i$ such that $a_i+b_i$ is a multiple of $f_i$ (namely, $b_i = f_i - a_i \bmod f_i$); then compute $\prod_i (a_i+b_i)$ and keep the smallest found so far. By construction, this will explore all possible solutions, and output the best one.

You can use the prime factorization of $c$ to help you enumerate all tuples $(f_1,\dots,f_D)$. In particular, the prime factorization makes it easy to enumerate all factors of $c$, so we can enumerate all possibilities for $f_1$ (namely, all factors of $c$), then enumerate all possibilities for $f_2$ (namely, all factors of $c/f_1$), etc.

The running time will be proportional to the number of such tuples you have to enumerate. This number is
$\prod_i {e_i + D - 1 \choose D - 1},$
which is not too bad if the number of prime factors of $c$ is small, but is horrible if $c$ has many prime factors.

StackExchange Computer Science Q#135173, answer score: 2