TARS's blog

Efficent solution(1.0 sec.) for counting divisiors
By TARS, history, 4 years ago, In English

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/)

Here is my solution)

I need a more efficient approach.

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think speeding up cin/cout (with ios_base::sync_with_stdio(false)) and avoiding unneeded long longs should be enough to AC.

      → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

Submission

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
#define vector<int> 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

→ Reply