Consider the problem of computing (x1 x2 ... xn)/x1, (x1 x2 ... xn)/x2,
..., (x1 x2 ... xn)/xn given x1, x2, ..., xn. Assume that n is a power
of 2.
For example, for n = 4, the problem is to compute x2 x3 x4, x1 x3 x4,
x1 x2 x4, x1 x2 x3, given x1, x2, x3, x4.
State an algorithm that solves this problem using n^{1+o(1)}
multiplications and no other x-dependent operations. State exactly how
many multiplications the algorithm uses, as a function of n.
Note that the time taken by the multiplications is not being counted.
Cost in this problem is measured by the number of multiplications. Note
also that divisions are not allowed.