Expert.
Put your skills to the test.

Problem summary

Count positive numbers in the inclusive interval [M,N] that equal y(y+1) for a positive integer y.

Constraints

1 ≤ M ≤ N; each endpoint has at most 100 decimal digits.

Worked example

Official sample; other valid outputs may exist.

1 20

4

Solution analysis

1. Define F(X) as the largest nonnegative integer y with y(y+1)≤X. Since these products increase strictly, F(X) also counts all positive qualifying products at most X. The answer is F(N)−F(M−1).
2. Use decimal strings for arbitrary-precision arithmetic. Binary search keeps a feasible lower bound zero and an infeasible upper bound 10^ceil(D/2), where D is the number of digits of X. Compare each midpoint’s exact product with X. Only comparison, addition, subtraction, multiplication, and division by two are required.
3. In [1,20], y=1,2,3,4 produce 2,6,12,20. Hence F(20)=4 and F(0)=0, giving four numbers.

Why it works

The product y(y+1) increases strictly for nonnegative y. The upper bound’s square exceeds every D-digit X, and zero is feasible. Each binary-search comparison preserves feasible lower and infeasible upper bounds until they differ by one, returning exactly F(X). The difference of the two prefix counts includes precisely products in [M,N].

Watch out. Fixed-width integers cannot store the endpoints. Include both endpoints and subtract the prefix count at M−1.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string normalize(string value){
    size_t first=value.find_first_not_of('0');
    if(first==string::npos){
        return "0";
    }
    return value.substr(first);
}
bool lessNumber(const string&left,const string&right){
    if(left.size()!=right.size()){
        return left.size()<right.size();
    }
    return left<right;
}
string addNumbers(const string&left,const string&right){
    string result;
    int i=static_cast<int>(left.size())-1;
    int j=static_cast<int>(right.size())-1;
    int carry=0;
    while(i>=0||j>=0||carry){
        int digit=carry;
        if(i>=0){
            digit+=left[i--]-'0';
        }
        if(j>=0){
            digit+=right[j--]-'0';
        }
        result.push_back(static_cast<char>('0'+digit%10));
        carry=digit/10;
    }
    reverse(result.begin(),result.end());
    return result;
}
// The caller guarantees left >= right.
string subtractNumbers(const string&left,const string&right){
    string result;
    int j=static_cast<int>(right.size())-1;
    int borrow=0;
    for(int i=static_cast<int>(left.size())-1;i>=0;--i){
        int digit=left[i]-'0'-borrow;
        if(j>=0){
            digit-=right[j--]-'0';
        }
        borrow=digit<0;
        if(borrow){
            digit+=10;
        }
        result.push_back(static_cast<char>('0'+digit));
    }
    reverse(result.begin(),result.end());
    return normalize(result);
}
string halfNumber(const string&value){
    string result;
    int remainder=0;
    for(char digit:value){
        int current=remainder*10+digit-'0';
        result.push_back(static_cast<char>('0'+current/2));
        remainder=current%2;
    }
    return normalize(result);
}
string multiplyNumbers(const string&left,const string&right){
    vector<int>digits(left.size()+right.size());
    for(int i=0;i<static_cast<int>(left.size());++i){
        for(int j=0;j<static_cast<int>(right.size());++j){
            digits[i+j+1]+=(left[i]-'0')*(right[j]-'0');
        }
    }
    for(int i=static_cast<int>(digits.size())-1;i>0;--i){
        digits[i-1]+=digits[i]/10;
        digits[i]%=10;
    }
    string result;
    for(int digit:digits){
        result.push_back(static_cast<char>('0'+digit));
    }
    return normalize(result);
}
string countUpTo(const string&limit){
    string low="0";
    // high is strictly above sqrt(limit), so high*(high+1) is infeasible.
    string high="1"+string((limit.size()+1)/2,'0');
    while(subtractNumbers(high,low)!="1"){
        string middle=halfNumber(addNumbers(low,high));
        string product=multiplyNumbers(middle,addNumbers(middle,"1"));
        if(!lessNumber(limit,product)){
            low=middle;
        }
        else{
            high=middle;
        }
    }
    // Exactly y=1,...,low produce positive products not exceeding limit.
    return low;
}
int main(){
    string lower,upper;
    cin>>lower>>upper;
    lower=normalize(lower);
    upper=normalize(upper);
    string beforeLower=subtractNumbers(lower,"1");
    cout<<subtractNumbers(countUpTo(upper),countUpTo(beforeLower))<<'\n';
}