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$

39%
Solution Ratio

solaimanopeEarliest,

upobirFastest, 0.3s

BigBagLightest, 53 MB

mahade31Shortest, 1534B

Toph uses cookies. By continuing you agree to our Cookie Policy.