2597 - Uri Online Judge - C++

Question

I’m doing a show in C++ to solve the 2597 platform math exercise URI ONLINE JUDGE follows below the description of the problem.

I started doing the program in C++, but realize that the input is too big, I tried to do a DP to pre-process everything before, but I can’t create a vector of size 10 9 !! Follow the program so you can take a look **

#include <bits/stdc++.h>
using namespace std;
typedef long long int bigint;

 bigint contaDiv(bigint dividendo) {

 bigint div = 0;
 bigint k = 1;
 bigint m = 1;
 bigint divisor = 1;

 while(divisor<=sqrt(dividendo))
  {

        if(dividendo%divisor==0)
        {
//              cout<<"(div/div)"<<(dividendo/divisor)<<endl;

            if((dividendo/divisor)==divisor)
            {
                div+=1;// cout<<"one"<<endl;
            }
            else
            {
                div+=2; //cout<<"two"<<endl;
            }

        }

        ++divisor;
}
return div;
}

int main(void) {

ios_base::sync_with_stdio(0);
cin.tie(0);

bigint c,n,vl;
cin>>c;


while(c--) {

    cin>>n;

    int ans = 0;

    for(int i=1;i<=n;++i) {
//          cout<<"DIV de "<<i<<" = "<<contaDiv(i)<<endl;
        if(contaDiv(i)%2==0) {
            ++ans;
        }
    }

    cout<<ans<<endl;
}

return 0;
}

**If anyone can give me a help... how to solve this problem !! At the moment this code is receiving Time Limit Exceed !! **

Answer 1

Your problem is a number factorization problem. The factorization problem is considered a difficult problem. But considering that N <= 10⁹, then the number cannot have divisors larger than sqrt(10⁹) = 31622 that is not himself, and with that, this limit of 31622 is actually a small and easy limit to be explored.

You are performing divisions by all numbers in the range of 1 up to the square root of the number. However, a better option is to divide only the prime numbers in this interval in order to assemble the factorization of the number and then count the number of factors. There are 3401 primes between 2 and 31622 (the largest is 31607).

First you can assemble a table of prime numbers. You can either mount this table at the beginning of the program whenever it runs or create another program to create this table and copy and paste it directly into the code.

Having the table of prime numbers, you can use it to factor a number and then count how many factors a number has, as outlined here.

By avoiding division by numbers that are not prime, you should avoid many divisions that would be useless.

With this approach, the upper limit for the number of divisions you would make would be 3401 + k divisions, where k is the number of prime factors found, which would be limited to log₂ n, which is something close to 30 in the worst case. Therefore, it is impossible that you have to perform more than 3431 divisions for any number of the entrance. This limit is somewhat loose, and the actual upper limit should be less than this. For the number 31607² = 999.002.449 it will take 3402 divisions. So you have somewhere between 3402 and 3431 divisions in the worst case. Compare this to what you had before, where you made 31622 rooms in the worst case.