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 | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | djm03178 | 152 |
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.
Name |
---|
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
(withios_base::sync_with_stdio(false)
) and avoiding unneededlong long
s should be enough to AC.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.me/blog/entry/83004?#comment-701983