<p>Let $S_0=\{1\}$. For $i = 1,...,n$, set $S_i\gets \{xy\mod b : x\in S_{i-1},y\in L_i\}$. Then just check whether $a \in S_n$.</p>

<p>It's obviously correct, since $S_i$ contains the residues which can be expressed as a product of elements, one each from $L_1,\ldots,L_i$.</p>

<p>Just using the definition of $S_i$ to compute it, you get a running time of $O(m n b)$, which is significantly better than brute force when $b$ is smaller than $n^m$.</p>

<p>By replacing the linear sweep by divide and conquer, you might be able to improve the running time even more, though I didn't check. (It will still have a factor of $b$ though.)</p>

CC BY-SA 3.0
2016-06-04T09:51:59.150Z
i think we cannot beat $n^m$ for this problem at large $b$.
Turbo
CC BY-SA 3.0
2016-06-04T07:30:01.660Z
2016-07-13T08:25:57.133Z
2016-07-13T08:25:57.133Z
Andrew Morgan
<p>The meet in the middle approaches that work in subset sum and k-sum should also work here with slight modifications.</p>

<p>It can be solved in $\tilde{O}\left(n^{m/2}\right)$ by constructing two lists $L_1$ and $L_2$ where $L_1$ is all possible products from first $m/2$ lists and $L_2$ is all possible products for last $m/2$ lists. Now we just need to check if there exist $p \in L_1 , q \in L_2$ such that $pq$ is $a\ mod\ b$. This can be done by first computing the inverse of one of the lists (in $\tilde{O}\left(n^{m/2}\right)$) and then checking if there is a common element in $\tilde{O}\left(n^{m/2}\right)$.</p>

<p>We can prove NP-hardness by reduction from <a href="https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete">subset-product problem</a>. For each integer $x_i, 1 \leq i \leq m$ in subset product instance create a list $(x_i , 1)$ with $n=2$. This only has a solution iff subset product had one(See Andrew's comment). Memebership in NP is trivial.</p>

CC BY-SA 3.0
2016-07-13T08:15:38.127Z
To clarify the NP-hardness reduction: If you try the natural-seeming choice of setting $b$ to be the target product and $a$ to be zero, then the reduction fails. Instead, one could pick $b$ to be larger than the product of all $x_i$, and pick $a$ to be the target product from the subset-product instance.
Andrew Morgan
CC BY-SA 3.0
2016-07-12T23:02:10.720Z
2016-07-13T08:43:51.403Z
2017-04-13T12:48:30.830Z
nikhil_vyas
<p>We have $m$ list of integers $L_1,\dots,L_m$ and each list $L_i$ contains $n$ distinct integers $L_i(1),\dots,L_i(n)$.</p>

<p>You are given two integers $a$ and $b$ with $b&lt;a$ and we know $n=O(2^{(\log b)^\alpha})$ and $m=O({(\log b)^\beta})$ for $0&lt;\alpha,\beta&lt;1&lt;\alpha+\beta$.</p>

<p>I want to check to see if I can pick one integer from each list to check if product mod $b$ is $a\bmod b$.</p>

<p>Is there a faster than $n^m$ brute force way to search for this? Is this NP hard (Andrew below sort of gives a pseudo polynomial algorithm)?</p>

<ds.algorithms><subset-sum>
Subset product problem
Turbo
# Subset product problem

(Asked by: username_0 on 2016-06-03)

We have $m$ list of integers $L\_1,\dots,L\_m$ and each list $L\_i$ contains $n$ distinct integers $L\_i(1),\dots,L\_i(n)$.

You are given two integers $a$ and $b$ with $b

I want to check to see if I can pick one integer from each list to check if product mod $b$ is $a\bmod b$.

Is there a faster than $n^m$ brute force way to search for this? Is this NP hard (Andrew below sort of gives a pseudo polynomial algorithm)?

**Tags:** ds.algorithms, subset-sum

---

## 2 answers

### Answer by username_1 on 2016-06-04. Score: 2

Let $S\_0=\{1\}$. For $i = 1,...,n$, set $S\_i\gets \{xy\mod b : x\in S\_{i-1},y\in L\_i\}$. Then just check whether $a \in S\_n$.

It's obviously correct, since $S\_i$ contains the residues which can be expressed as a product of elements, one each from $L\_1,\ldots,L\_i$.

Just using the definition of $S\_i$ to compute it, you get a running time of $O(m n b)$, which is significantly better than brute force when $b$ is smaller than $n^m$.

By replacing the linear sweep by divide and conquer, you might be able to improve the running time even more, though I didn't check. (It will still have a factor of $b$ though.)

> **Comments:**
> **username_0**: i think we cannot beat $n^m$ for this problem at large $b$.  

---

### Answer by username_2 on 2016-07-12. Score: 1

The meet in the middle approaches that work in subset sum and k-sum should also work here with slight modifications.

It can be solved in $\tilde{O}\left(n^{m/2}\right)$ by constructing two lists $L\_1$ and $L\_2$ where $L\_1$ is all possible products from first $m/2$ lists and $L\_2$ is all possible products for last $m/2$ lists. Now we just need to check if there exist $p \in L\_1 , q \in L\_2$ such that $pq$ is $a\ mod\ b$. This can be done by first computing the inverse of one of the lists (in $\tilde{O}\left(n^{m/2}\right)$) and then checking if there is a common element in $\tilde{O}\left(n^{m/2}\right)$.

We can prove NP-hardness by reduction from [subset-product problem](https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete). For each integer $x\_i, 1 \leq i \leq m$ in subset product instance create a list $(x\_i , 1)$ with $n=2$. This only has a solution iff subset product had one(See Andrew's comment). Memebership in NP is trivial.

> **Comments:**
> **username_1**: To clarify the NP-hardness reduction: If you try the natural-seeming choice of setting $b$ to be the target product and $a$ to be zero, then the reduction fails. Instead, one could pick $b$ to be larger than the product of all $x_i$, and pick $a$ to be the target product from the subset-product instance.  

---

