https://www.codechef.com/LOCSEP17/problems/JMAGNUM/
I got TLE on cases >10^3. Please someone help me understand the solution.
3 precomputations will be needed.
-
precompute all the primes first. O(nloglogn)
-
then precompute the sum of digits for every prime.
precomuptation will take O(logn) for every prime number that you have already calculated from the sieve above. -
then precompute your ans for every query from 0 to iā¦ and then just print ans[r]-ans[l-1].
well written code :
[1]
[1]: https://www.codechef.com/viewsolution/15566762
1 Like
You can use a sieve and for each prime, instead of just using a flag to mark it as prime or not, you can store the sum of the prime divisors. After that you can take the prefix sum to answer each test case in O(1).
My solution: https://www.codechef.com/viewsolution/15554267
In my solution, initially ans[i] stores the sum of digits of prime divisors of i, then I take the prefix sum in the second loop. isprime[i]==1 if i is prime else 0.