Avoid time limit of odd number of odd divisors

Question

The problem set was on a contest: Given a range [L, R], find the number of integers in that range which have an odd number of odd divisors. For example, 1 has only one divisor and it is odd, 9 has three divisors {1, 3, 9} and all of them are odd. Meanwhile, 18 has six divisors {1, 2, 3, 6, 9, 18} but three of them are odd. So 1, 9 and 18 have an odd number of odd divisors.

Input Input will start with a positive integer T (T ≤ 105) denoting the number of test cases. Each test case will have two positive integers L, R (1 ≤ L ≤ R ≤ 1018), the range.

Output For each test case, the first line will be the case number in the format “Case t: x” without the quotes. Here t is the case number starting from 1 and x is the number of integers that fall in the range [L, R] and have an odd number of odd divisors.

Sample

Input   Output

3

1 3

5 10

10 15   


Case 1: 2

Case 2: 2

Case 3: 0

What I code:

#include <bits/stdc++.h>
#include <cmath>
using namespace std;

int main()
{
    int T;
    cin>>T;

    for(int j=0; j<T; j++)
    {
        int m, nx;
        cin>>m>>nx;
        int finalCount = 0;

        for(int kk=m; kk<nx; kk++) // number
        {
            // Note that this loop runs till square root
            int oddCounter = 0;
            for (int i=1; i<=sqrt(kk); i++)
            {
                if (kk%i == 0)
                {
                    // If divisors are equal, print only one
                    if (kk/i == i)
                    {
                        if (kk & 1)
                            oddCounter++;
                    }
                    else // Otherwise print both
                    {
                        if (i & 1)
                            oddCounter++;
                        if ((kk/i) & 1)
                            oddCounter++;

                    }
                }
            }

            if ( oddCounter& 1)
                finalCount++;
        }

        cout<<"Case "<<j+1<<": "<<finalCount<<"\n";

    }

    //auto var_name = 0;
    //cout<<var_name<<"\n";

}

But got time limit exceeded.

CPU: 2s

Memory: 1500MB

How can I improve my code? Any suggestion?

You can simply try to iterate over all odd numbers and count in table number of dividors. sth like for(int i=1; i<=r ; i+=2) for(int j=i; j<=r; j+=i) dividors[j]++; and then check how many numbers in range are odd. You avoid time-consuming divisions :) — Karol T., Oct 05 '18 at 12:27
Unrelated to your problem, but please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Some programmer dude, Oct 05 '18 at 12:33
I would suggest creating a 2D array with all related divisors. For instance, you find that 9 has the divisors 1, 3 and 9 which you store in the array at index 9. Later on you check 18 and find that it has the divisors 18, 6 and 9, 3, 1 which you have already calculated earlier which they are. In that way you don't need to calculate all divisors everytime you find one. — Johan, Oct 05 '18 at 13:17
constraints are T<=10^5 and 1<=L<=R<=10^18 not 105 and 1018. [problem link](https://algo.codemarshal.org/contests/icpc-dhaka-preli-18/problems/C) — sabertooth, Sep 24 '19 at 13:47

Avoid time limit of odd number of odd divisors

0 Answers0