You are not logged in. Please login at www.codechef.com to post your questions!

×

JMAGNUM , LOC2017 need help

https://www.codechef.com/LOCSEP17/problems/JMAGNUM/ I got TLE on cases >10^3. Please someone help me understand the solution.

asked 03 Oct '17, 14:31

mysterion's gravatar image

1★mysterion
32
accept rate: 0%


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.

link

answered 03 Oct '17, 14:37

ista2000's gravatar image

4★ista2000 ♦
2.4k722
accept rate: 20%

edited 03 Oct '17, 16:03

3 precomputations will be needed.

  1. precompute all the primes first. O(nloglogn)

  2. 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.

  3. then precompute your ans for every query from 0 to i.. and then just print ans[r]-ans[l-1].

well written code : CODE

link

answered 03 Oct '17, 14:36

goyal_banna's gravatar image

3★goyal_banna
585414
accept rate: 8%

edited 03 Oct '17, 14:37

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×301
×198
×30

question asked: 03 Oct '17, 14:31

question was seen: 249 times

last updated: 03 Oct '17, 20:08