GCD and Sum

upobir Criterion 2021 Round 12

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


39% Solution Ratio
solaimanopeEarliest, Apr '21
upobirFastest, 0.3s
BigBagLightest, 53 MB
mahade31Shortest, 1534B
Toph uses cookies. By continuing you agree to our Cookie Policy.