CODEWITHSUNDEEP
c++algorithmtime
Mahendra Chandwani
Mahendra Chandwani

Reputation: 70

how to reduce execution time

Currently the following problem is taking 3.008** seconds to execute for some testcase provided on hackerearth.com where allowed time is 3.0 seconds so i get time limit error. Please help to reduce execution time.

Problem: Alice has just learnt multiplying two integers. He wants to multiply two integers X and Y to form a number Z.To make the problem interesting he will choose X in the range [1,M] and Y in the range [1,N].Help him to find the number of ways in which he can do this.

Input

First line of the input is the number of test cases T. It is followed by T lines. Each line has three space separated integers, the numbers Z, M and N.

Output

For each test case output a single integer, the number of ways.

Constraints 1 <= T <= 50 1 <= Z <= 10^12 1 <= M <= 10^12 1 <= N <= 10^12

CODE:

#include <iostream>
using namespace std;


int chk_div(long long a,long long b)
{
if(((a/b) * (b) )==a)return 1;
return 0;
}

int main()
{
   int t;
   long  i,j,count;
   long  n,m,z;
   cin>>t;
   while(t--)
   {count=0;
    cin>>z>>m>>n;
    if(m>z)m=z;
    if(n>z)n=z;
    if (m>n)m=n;
    for(i=1;i<=m;i++)
    {
         if(chk_div(z,i))count++;       
     }

   cout<<count<<"\n";
   }
return 0;
}

Upvotes: 2

Views: 3318

Answers (4)

smac89
smac89

Reputation: 43078

I believe this should get the job done (idea from @zch's answer):

#include <iostream>
#include <cmath>

auto MAX = [] (int A, int B) -> bool { return A > B ? A : B; };
auto MIN = [] (int A, int B) -> bool { return A < B ? A : B; };

using std::cout;
using std::cin;

int main() {
    long long Z, M, N, T, low, high, temp, div;
    int ans;

    for (cin >> T; T--; ) {

        cin >> Z >> M >> N;
        temp = MIN(M, N);
        low = MIN(sqrt(Z), temp);
        high = MAX(M, N);

        for( ans = 0; low > 0 && (Z / low) <= high; --low ) {
            if ( Z % low == 0) {
                ++ans;
                div = Z / low;
                ans += (div != low && div <= temp);
            }
            //cout << temp << " * " << Z / temp << " = " << Z << "\n";
        }
        cout << ans << "\n";
    }

    return 0;
}

Will be adding comments in a bit

Code with comments:

#include <iostream>
#include <cmath>

auto MAX = [] (int A, int B) -> bool { return A > B ? A : B; };
auto MIN = [] (int A, int B) -> bool { return A < B ? A : B; };

using std::cout;
using std::cin;

int main() {
    long long Z, M, N, T, low, high, temp, div;
    int ans;

    for (cin >> T; T--; ) {

        cin >> Z >> M >> N;
        temp = MIN(M, N);
        low = MIN(sqrt(Z), temp);//Lowest value <--We start iteration from this number
        high = MAX(M, N); //Maximum value

        for( ans = 0; low > 0 && (Z / low) <= high; --low ) {

            //Number of things going on in this for-loop
            //I will start by explaining the condition:
                //We want to keep iterating until either low is below 1
                // or when the expression (Z / low) > high.
                //Notice that as the value of low approaches 0,
                //the expression (Z / low) approaches inf
            if ( Z % low == 0) {

                //If this condition evaluates to true, we know 2 things:
                    /*Z is divisible by this value of low and 
                        low is in the range of MIN(M,N) <--true*/
                    /*Because of our condition, (Z / low) is
                        within the range of MAX(M, N) <--true*/
                ++ans;
                div = Z / low;

                //This second part checks if the opposite is true i.e.
                    /*the value of low is in the range of
                        MAX(M, N) <--true*/
                    /*the value (Z / low) is in the range of
                        MIN(M, N) <--true only in some cases*/
                ans += (div != low && div <= temp);

                //(div != low) is to avoid double counting
                /*An example of this is when Z, M, N have the values:
                    1000000, 1000000, 1000000
                    The value of low at the start is 1000 */
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Upvotes: 5

Jarod42
Jarod42

Reputation: 217085

In fact, you have to resolve the problem in a different way:

find the Prime decomposition:

so Z = A^a * B^b * ... * P^p with A, B, .., P prime numbers

and so you just have to compute the number of possibilities from a, b, ... p.

(So the result is up to (1 + a) * (1 + b) * ... * (1 + p) depending of M&N constraints).

Upvotes: 2

Juniar
Juniar

Reputation: 1389

  • Your if(((a/b) * (b) ) == a) return 1; will always return 1. Why are you dividing A with B (a/b) then multiply the result by B. This is ambiguous because, your answer will be A. when you say, (a/b) * (b). B`s will cancel each other out and you are left with A as your answer. And so basically you are comparing if A == A, which is true.

Upvotes: -1

zch
zch

Reputation: 15278

The main problem with performance here is the fact that your inner loop does about 10^12 iterations. You can reduce it a million times to sqrt(z) <= 10^6.

The trick here is to notice that Alice can write z = x * y if and only if he can write z = y * x. Also, either x <= sqrt(z) or y <= sqrt(z). Using these facts you can iterate only up to square root of z to count all cases.

Upvotes: 8

Related Questions