# Editorial for GCD and Sum

Use sieve to keep track of prime factorization of numbers $1$ to $2 \cdot 10^5$ . Then for all primes, keep track of the indices that have their multiples. Then for sum and querying you can use a segment tree. And to update, use the multiple list to only update those values that have gcd > 1. A number will be updated at most $\log n$ times, so the solution is $n \log^2 n$

### Statistics

39% Solution Ratio

solaimanopeEarliest, 5M ago

upobirFastest, 0.3s

BigBagLightest, 53 MB