1381. The gcd of Everything Except One
Given n values, print for each position the gcd of all the other values.
12 18 24 30 -> 6 6 6 6
6 10 -> 10 6
7 -> 0
With n = 1 the answer is the gcd of nothing. That is defined here as 0,
which is the standard choice because gcd(0, v) is v for every v, so 0
is the identity the fold starts from. The statement settles it rather than
leaving it to taste, since all five reference solutions would otherwise
disagree.
## What most people try first
For each position, fold a gcd over the other n-1 values. That is O(n^2)
gcd calls, about 4 * 10^10 at n = 200000.
## Prefix and suffix
Problem 1330 prints the gcd of every prefix. Build that, and the suffix version too:
``` pre[i] = gcd of values 0 .. i-1 pre[0] = 0 suf[i] = gcd of values i .. n-1 suf[n] = 0
answer[i] = gcd(pre[i], suf[i+1]) ```
values 12 18 24 30
pre 0 12 6 6 6
suf 6 6 24 30 0
answer 6 6 6 6
## Why that is correct
gcd is associative and commutative, so the gcd of a set can be computed by
splitting the set anywhere and combining the two parts. The values other than
position i are exactly the prefix before i together with the suffix after
i, which are disjoint and cover everything else. Starting both folds from 0
is what makes the empty prefix and the empty suffix behave: gcd(0, v) = v, so
an empty side contributes nothing.
## Overflow
Nothing here can overflow, and it is worth saying why rather than assuming it.
A gcd divides both its arguments, so it is never larger than either of them. As
every value is at most 10^9, every prefix, suffix and answer is at most
10^9, which fits in a signed 32-bit integer since INT_MAX is 2147483647.
This problem is the exception in this block: there is no product anywhere, so
there is no 10^18 intermediate to protect. A JavaScript Number is exact
here too, provided no bitwise operator is used, since those truncate to 32 bits
and 10^9 survives that only by luck of its size.
## Cost
O(n log V), one pass each way.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each value ≤ 1000000000` - The gcd of the empty set is `0`.
Input
The first line contains n.
The second line contains n integers.
Output
Print n integers on one line, separated by single spaces. The ith is the gcd of every value except the ith. For n = 1 print 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.