ashishranjan2828's blog

http://www.spoj.com/problems/FACTDIV/

By ashishranjan2828, history, 7 years ago, In English

I'm getting tle with normal divisor algorithm. Is there some extra needed concept required for this problem..

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

You should fill a dp ( dp[i] = number of divisors of i) before getting tests.

Then use partial sum on dp and answer each query in O(1).

So similar to 546D - Солдат и игра с числами.

So use a fast input ouput like scanf printf.

→ Reply