count_divisors.cpp

#include<iostream>
#include<vector>
#include<tuple>
#include<cmath>

template<typename Integer, typename Result = Integer>
constexpr Result sqrt_floor(const Integer& n){
    if(n <= 1)return n;
    Integer r(sqrt(n));
    do r = (r & n / r) + (r ^ n / r) / 2; while(r > n / r);
    return r;
}
template<typename Integer>
constexpr bool is_inside(const Integer& x, const Integer& y, const Integer& n){
    return !x || y >= (n + x - 1) / x;
}
template<typename Integer>
constexpr bool is_cross(const Integer& x, const Integer& y, const Integer& a, const Integer& b, const Integer& n){
    if(a == 0 || b == 0)return a * y > b * x;
    return a * y > b * x && sqrt_floor(4 * a * b * (n - x * y)) <= std::max(a * y, b * x) - std::min(a * y, b * x);
}
constexpr unsigned long next_in(const unsigned long& x, const unsigned long& y, const unsigned long& a, const unsigned long& b, const unsigned long& n){
    if(b == 0)return (n - x * y + a * y - 1) / (a * y);
    return (a * y - sqrt_floor<__uint128_t, unsigned long>(static_cast<__uint128_t>(b * x + a * y) * (b * x + a * y) - static_cast<__uint128_t>(4) * a * b * n) - b * x + 2 * a * b - 1) / (2 * a * b);
}
constexpr unsigned long next_out(const unsigned long& x, const unsigned long& y, const unsigned long& a, const unsigned long& b, const unsigned long& n){
    if(a == 0)return (x * y - n) / (x * b);
    return (a * y + sqrt_floor<__uint128_t, unsigned long>(static_cast<__uint128_t>(b * x + a * y) * (b * x + a * y) - static_cast<__uint128_t>(4) * a * b * n) - b * x) / (2 * a * b);
}

template<typename Integer>
Integer count_divisors(const Integer& X){
    using namespace std;
    using integer_type = Integer;

    using subtree_type = std::tuple<integer_type, integer_type, integer_type, integer_type>;
    vector<subtree_type> stern_brocot_tree{{1, 0, 0, 1}, {0, 1, 0, 0}};

    using point_type = std::pair<integer_type, integer_type>;
    point_type now_point{1, X};

    Integer result{X - 1};

    while(now_point.first <= X){
        auto& [x, y]{now_point};

        // subtree between a/b and c/d
        auto [a, b, c, d]{stern_brocot_tree.back()};
        stern_brocot_tree.pop_back();

        if(b == 0)break;

        // next vertex of convex hull
        const auto n_upper{next_out(x, y, a, b, X)};
        result += a * n_upper * y - ((a * n_upper + 1) * (b * n_upper + 1) + n_upper) / 2;
        x += n_upper * a;
        y -= n_upper * b;

        // backtrack
        while(!empty(stern_brocot_tree)){
            tie(a, b, c, d) = stern_brocot_tree.back();
            if(is_inside(x + a, y - b, X))break;
            stern_brocot_tree.pop_back();
        }

        if(empty(stern_brocot_tree))break;

        // search forward
        while(y > d){
            if(y > b + d && is_inside(x + a + c, y - b - d, X)){
                const auto n_lower{next_out(x + a + c, y - b - d, c, d, X)};
                tie(a, b, c, d) = make_tuple(a + c * (n_lower + 1), b + d * (n_lower + 1), a + c * (n_lower + 2), b + d * (n_lower + 2));
            }else if(is_cross(x + c, y - d, a, b, X)){
                const auto n_lower{next_in(x + c, y - d, a, b, X)};
                if(y < b * n_lower + d || !is_inside(x + a * n_lower + c, y - b * n_lower - d, X))break;
                tie(a, b, c, d) = make_tuple(a * n_lower + c, b * n_lower + d, a * (n_lower - 1) + c, b * (n_lower - 1) + d);
            }else break;
            stern_brocot_tree.emplace_back(a, b, c, d);
        }
    }

    return result;
}

int main(){
    using namespace std;
    using integer_type = unsigned long;

    integer_type N, M;
    cin >> N >> M;
    cout << count_divisors(M + 1) - count_divisors(N) << endl;

    return 0;
}