_viiku's blog

By _viiku, history, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _viiku (previous revision, new revision, compare).

»
4 weeks 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.

»
4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks 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.

  • »
    »
    4 weeks 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)

    • »
      »
      »
      4 weeks 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.

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _viiku (previous revision, new revision, compare).

»
4 weeks 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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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

»
4 weeks 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