Number of numbers in [L, R] with an odd number of odd factors

Question

I was doing this competetive programming task, and even though I think I have an asymptotically optimal solution I'm still getting time limit exceeded. You need to register an account to see the problem statement and submit, so I will restate it here:

Given a range [L, R], find the number of integers in that range which have an odd number of odd divisors.

Constraints are 1 <= L <= R < 10^18, and there are up to 10^5 such queries.

Example:

The solution for [1, 18] is 7, because there are 7 numbers with an odd number of odd divisors within that range:

1 - (1)
2 - (1, 2)
4 - (1, 2, 4)
8 - (1, 2, 4, 8)
9 - (1, 3, 9)
16 - (1, 2, 4, 8, 16)
18 - (1, 2, 3, 6, 9, 18)

My code and idea:

We know that divisors come in pairs, so any odd number that has an odd number of divisors must be a square number. Any even number with an odd number of divisors must have some odd "base" that has an odd number of divisors, and for this "base" to do that it must be a square number like previously discussed.

Essentially we are looking for numbers that are in the form of O^2 * 2^N, where O is some odd number. I treat the solution to [L, R] as [1, R] - [1, L), and then iterate over all 2^N and get the number of O that can fit under the number.

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

typedef long long ll;
// number of numbers matching criteria on [1, n]
ll n_under(ll n){
    ll res = 0;
    while(n){
        res += (sqrt(n) + 1ll)/2ll;
        n /= 2ll;
    }
    return res;
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    cin >> q;
    for(int i = 1; i <= q; ++i){
        ll l, r;
        cin >> l >> r;
        cout << "Case " << i << ": " << (n_under(r) - n_under(l - 1)) << endl;
    }
    return 0;
}

I'm getting a TLE for the for the first test set, and I'm unsure as to why. I'm looking for any asymptotic improvements or constant-factor optimizations.

Answer 1

Well the trick is to notice that such numbers are either squares or 2*square. (Or find first few of such numbers and check OEIS)

Knowing this we can easily calculate count of such numbers in interval in O(1) so we can answer all queries in O(Q).

1. First for calculating range [L,R] we can calculate ranges [0,R] - [0,L-1]

2. For Some range [0,X] we can notice that there's sqrt(X) squares in this interval

3. Similar for double squares, theres roughly sqrt(X/2) such numbers

4. Sqrt for large numbers in C++ is not that precise, so we might need to add some +-1 for sqrt calculations

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll solve(ll x)
{
    ll sq = sqrt(x)+2;
    while(sq*sq > x)sq--;

    ll sq2 = sqrt(x/2)+2;
    while(2*sq2*sq2 > x)sq2--;

    return sq + sq2;
}

ll solve(ll l, ll r)
{
    return solve(r) - solve(l-1);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll q,l,r,cs=1;
    cin>>q;
    while(q--)
    {
        cin>>l>>r;
        cout<<"Case "<<cs++<<": "<<solve(l,r)<<"\n";
    }
}