### _viiku's blog

By _viiku, history, 4 weeks ago,

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.

• +16

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by _viiku (previous revision, new revision, compare).
 » 4 weeks ago, # |   +3 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.
 » 4 weeks ago, # |   +8 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.
•  » » 4 weeks ago, # ^ |   -8 Well, this works only for small factors, large primes factors won't work efficiently.
 » 4 weeks ago, # |   +1 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.
•  » » 4 weeks ago, # ^ |   0 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)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I think speeding up cin/cout (with ios_base::sync_with_stdio(false)) and avoiding unneeded long longs should be enough to AC.
•  » » » » 4 weeks ago, # ^ |   0 Yeah,i got AC. i added that line and changed long long int to int. Thank you..
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by _viiku (previous revision, new revision, compare).
 » 4 weeks ago, # | ← Rev. 4 →   +15 There is also a very well known algotithm to compute divisors of all numbers $\le x$ in $O(x\log x)$. for(int i=1;i<=x;i++){ for(int j=i;j<=x;j+=i){ divisors[j].push_back(i); } } 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
•  » » 4 weeks ago, # ^ |   +8 I don't understand how that turns out to be $O(xH_x)$, shouldn't it be for (int i = 1; i <= x; i++) { for (int j = i; j <= x; j += i) { divisors[j].push_back(i); } } I.e., we increment $j$ by $i$, not by $1$.Otherwise the complexity seems quadratic to me.
•  » » » 4 weeks ago, # ^ |   0 You are correct. I really need to stop making mistakes. Corrected in OP.
 » 4 weeks ago, # |   -8 I used Pollard Rho's factoring with Miller Rabin primality test. I took the factoring from one of dacin21's submissions.Submission
•  » » 4 weeks ago, # ^ |   0 Would you explain it a bit? There're lots of code.
•  » » » 4 weeks ago, # ^ |   0 Which part?
 » 4 weeks ago, # |   0 #define vector vi; vi v(N+1,0); void factorize (vi v){ for(int i=1;i<=N;i++) for(int j=i;j<=N;j+=i){ v[j]+=1; } return v; } 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
•  » » 4 weeks ago, # ^ |   0 I think this is the same as the one mentioned earlier in this thread. https://codeforces.com/blog/entry/83004?#comment-701983