Primera Subtarea:

Cada vez que se vaya a añadir un número, contamos los coprimos con él con un ciclo, y lo marcamos, al retirar un número, descontamos los coprimos con él de la misma manera y lo desmarcamos, complejidad ~O(n^2\log{n})~.

Nota adicional interesante: Se puede precalcular el ~gcd~ de todos los pares de enteros hasta ~n~ en ~O(n^2)~ de con una criba, cuando vayas por ~gcd(i, j)~, asegura haber calculado todos los ~gcd(x, y)~ tal que ~1 \leq x < i~ y ~1 \leq y < j~. Toma el menor primo que divida a i y la cantidad de veces que está, y quítelo (dividiendo por ~p^k~), y haga lo mismo con j, luego pregunte por ~gcd(\frac{i}{p^k},\frac{j}{p^q})~ que ya está calculado y multiplíquelo por ~p^{min(k, q)}~.

Segunda Subtarea:

Div1C-Mike_and_foam