Intermediate.
Put your skills to the test.

Problem summary

Count integers x in [M,N] expressible as y(y+1) with y>1. The two consecutive factors must both be proper divisors.

Constraints

2 ≤ M ≤ N ≤ 10^15.

Worked example

Input and output for the worked example discussed below.

10 20

2

Solution analysis

1. For y≥2, y and y+1 are proper divisors of y(y+1). Different y give different products because y(y+1) is strictly increasing, so count valid factor choices rather than scanning a huge interval.
2. Let F(B) count products at most B. Binary-search the largest y with y(y+1)≤B. Then F(B)=max(0,y−1), since the permitted y values start at2. The interval answer is F(N)−F(M−1).
3. In [10,20], y=3 and4 give12 and20. Their products lie inside the inclusive interval, while y=2 gives6 below it and y=5 gives30 above it. The answer is2.

Why it works

The factor characterization is necessary and sufficient, and strict monotonicity gives exactly one product per permitted y. Binary search finds the final valid y, so the prefix count is exact; subtracting prefix counts isolates the inclusive interval.

Watch out. Exclude y=1 because its factor1 is not a proper divisor under the definition. Use M−1 for the lower prefix, and avoid overflow when comparing products.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
using namespace std;
long long countThrough(long long bound){
    if(bound<6){
        return 0;
    }
    long long low=1;
    long long high=1000000000;
    while(low<high){
        long long middle=low+(high-low+1)/2;
        // Division compares the product without risking multiplication overflow.
        if(middle<=bound/(middle+1)){
            low=middle;
        }
        else{
            high=middle-1;
        }
    }
    return max(0LL,low-1);
}
int main(){
    long long m;
    long long n;
    cin>>m>>n;
    cout<<countThrough(n)-countThrough(m-1)<<'\n';
}