**Response to the original question.** The original problem was to design a fast algorithm which decides whether the system above is solvable.

Note that the system of two congruences $x\equiv a_1\pmod{c_1}$, $x\equiv a_2\pmod{c_2}$ is solvable (and solution is unique modulo $\operatorname{lcm}(c_1,c_2)$ if and only if $a_1\equiv a_2\pmod{\gcd(c_1,c_2)}$.

At the beginning we have $n$ moduli $c_j$ and $n$ arrays $a_j=(a_j^0,a_j^1)$ of length 2, for $j=1,\dots,n$. We will also need the $2n$ by $2n$ "tiedness" matrix, which has initially all entries zero. We simply run a double loop over all pairs $i\ne j$, and on each step we do the following:

(1) Compute $c_{ij}=\gcd(c_i,c_j)$.

(2) Verify the congruences $a_i^k\equiv a_j^l\pmod{c_{ij}}$ where $a_i^k$ and $a_j^l$ run over all elements of arrays $a_i$ and $a_j$, respectively. (Note that there could be less than two elements in an array! See the next step.)

(3) If for a certain $k$ each of the congruences $a_i^k\equiv a_j^l\pmod{c_{ij}}$ is violated for all $a_j^l$, then remove $a_i^k$ from array $a_i$ and all other $a_q^p$ (from the corresponding $a_q$) which are tied to $a_i^k$ (the corresponding entry for this pair is set to be 1). Similarly, if for a certain $l$ each of the congruences $a_i^k\equiv a_j^l\pmod{c_{ij}}$ is violated for all $a_i^k$, then remove $a_j^l$ from array $a_j$ and all other $a_q^p$ (from the corresponding $a_q$) which are tied to $a_j^l$.

(4) Note that in the case of *four* congruences on step (3), if three are valid then the fourth one holds automatically. There are however two cases when we have only two of the four congruences $a_i^k\equiv a_j^l\pmod{c_{ij}}$ but all four elements from $a_i$ and $a_j$ are left after step (3). For these two cases we make the corresponding pairs $(a_i^k,a_j^l)$ "tied" by putting on the corresponding places in the tiedness matrix ones. The tiedness relation is further distributed along the matrix as equivalence relation, so that we put extra 1s for $a_i^k$ to reflect the tied partners of $a_j^l$, and similarly for $a_j^l$.

If at the end or at any of the steps you realize that at least one of the arrays is empty, terminate with the result "no such $m$ exists". If each of the arrays is nonempty, then the solution $m$ exists and can be obtained from the Chinese residue theorem by picking an *arbitrary* element from each array.

**Edit.** The author disappeared for a couple of days and came back with a different question. He does not need an algorithm any more but an explicit formula which says whether the system is solvable or not.

Dear Marc, this is exactly the same question(!), believe you or not. An algorithm is that explicit formula, and if there exists another one, it can be programmed and will become another algorithm. There is some heuristical evidence of why the things cannot be faster. And please make clear next time, before rewriting a question, what do you wish to get, why do you wish to get it (your motivation), and what is unsatisfactory in others' responses. This will be at least fair.