I've tried to solve this using sieve and prime factorization but I got TLE for some cases. Here is the CSES problem:) (https://cses.fi/problemset/task/1713/)

I need a more efficient approach.

# | User | Rating |
---|---|---|

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 199 |

3 | SecondThread | 195 |

4 | vovuh | 189 |

5 | antontrygubO_o | 186 |

5 | Um_nik | 186 |

7 | pikmike | 184 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

I've tried to solve this using sieve and prime factorization but I got TLE for some cases. Here is the CSES problem:) (https://cses.fi/problemset/task/1713/)

I need a more efficient approach.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/26/2020 13:27:17 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by _viiku (previous revision, new revision, compare).Why do you need the primes? You just need to precalculate using sieve. Anyway, this problem is pretty well known. You can easily find the solution on the internet.

You can solve this task using sieve in O(x log log x + N log x). You don't need different approach here.

If you are very interested, there is a method how to calculate all the divisors of the number in... well, something like O(n^(1/4)*log^2) using this algorithm.

But this task can be esily solved with sieve.

Well, this works only for small factors, large primes factors won't work efficiently.

Naive O(NsqrtX) should work since X=10^6 and N=10^5 (so 10^8 operations). I'm calling sqrtX naive because it's pretty well known.

At least, I did that and got AC, so it should probably work for you.

When I saw constraints, I also thought about sqrt implementation [but it didn't work for me for some cases though.] Here is my sqrt(x) solution. (https://ideone.com/XRfRBn)

I think speeding up

`cin/cout`

(with`ios_base::sync_with_stdio(false)`

) and avoiding unneeded`long long`

s should be enough to AC.Yeah,i got AC. i added that line and changed long long int to int. Thank you..

Auto comment: topic has been updated by _viiku (previous revision, new revision, compare).There is also a very well known algotithm to compute divisors of all numbers $$$\le x$$$ in $$$O(x\log x)$$$.

This is $$$O(xH_x)$$$, which is well known to be $$$O(x\log x)$$$. This not only computes the number of divisors, but also stores all of them for all numbers.

Just in case you don't know $$$H_x$$$ you can read this

I don't understand how that turns out to be $$$O(xH_x)$$$, shouldn't it be

I.e., we increment $$$j$$$ by $$$i$$$, not by $$$1$$$.

Otherwise the complexity seems quadratic to me.

You are correct. I really need to stop making mistakes. Corrected in OP.

I used Pollard Rho's factoring with Miller Rabin primality test. I took the factoring from one of dacin21's submissions.

Submission

Would you explain it a bit? There're lots of code.

Which part?

I used this to count the number of divisors for Atcoder Beginner Contest. Worked for me this is a similar to seive so i guess runtime is same as seive

I think this is the same as the one mentioned earlier in this thread. https://codeforces.com/blog/entry/83004?#comment-701983