Given n elements and m add and delete queries, you are to output the number of coprime pairs after each query.
Note that we can use answers to the previous query to answer the current query. We only need to add/subtract the number of coprime numbers to/from the previous answer.
For example, when given a number 6, we need to find how many numbers are coprime to 6. Let f(x) be the number of integers that are multiples of x, and with the inclusion-exclusion principle, we can write the number of coprimes of 6 as f(1)-f(2)-f(3)+f(6).
Observing the above formula, we can find out that the coefficients satisfy the mobius function, and we can speed up the algorithm by using it.
To calculate the mobius function values, we can let mobius(1)=1, and subtract it from mobius(i * j) for j>1.