Editorial for GCD and Sum

Use sieve to keep track of prime factorization of numbers 11 to 21052 \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 logn\log n times, so the solution is nlog2nn \log^2 n

    Statistics


    39% Solution Ratio

    solaimanopeEarliest, 5M ago

    upobirFastest, 0.3s

    BigBagLightest, 53 MB

    mahade31Shortest, 1534B

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