1fe9ecdb.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 500000 + 5;
const size_t P = 41538 + 5;

bool notPrime[N];
vector<int> prime;
int d[N];

inline void prepare()
{
    static int g[N]; // 最小质因子的次数

    prime.reserve(P);
    notPrime[1] = true;
    d[1] = 1;

    for (int i = 2; i < N; ++i)
    {
        if (!notPrime[i])
        {
            prime.emplace_back(i);
            d[i] = 2;
            g[i] = 1;
        }
        for (const auto &p : prime)
        {
            if (i * p >= N)
            {
                break;
            }
            notPrime[i * p] = true;
            if (i % p == 0)
            {
                d[i * p] = d[i] / (g[i] + 1) * (g[i] + 2);
                g[i * p] = g[i] + 1;
                break;
            }
            else
            {
                d[i * p] = d[i] * 2;
                g[i * p] = 1;
            }
        }
    }
}

namespace FFT
{
    struct Comp
    {
        f64 r, i;

        inline Comp() {}
        inline Comp(const f64 &r, const f64 &i)
        {
            this->r = r;
            this->i = i;
        }
        inline Comp operator+(const Comp &rhs) const
        {
            return (Comp){this->r + rhs.r, this->i + rhs.i};
        }
        inline Comp operator-(const Comp &rhs) const
        {
            return (Comp){this->r - rhs.r, this->i - rhs.i};
        }
        inline Comp operator*(const Comp &rhs) const
        {
            return (Comp){this->r * rhs.r - this->i * rhs.i,
                          this->r * rhs.i + this->i * rhs.r};
        }
        inline const Comp &operator*=(const Comp &rhs)
        {
            return *this = *this * rhs;
        }
    };

    const int L = 20;
    const int LIM = 1 << L;
    const int S = LIM + 5;

    const f64 PI = 3.14159265358979323846;
    const Comp BASE = Comp(1.0, 0.0);

    Comp A[S];
    int R[S], ans[S];

    inline void fft(Comp *J, int sign)
    {
        for (int i = 0; i < LIM; ++i)
        {
            if (i < R[i])
            {
                swap(J[i], J[R[i]]);
            }
        }
        for (int i = 1; i < LIM; i <<= 1)
        {
            Comp T(cos(PI / i), sign * sin(PI / i));
            for (int j = 0; j < LIM; j += (i << 1))
            {
                Comp t(BASE);
                for (int k = 0; k < i; ++k, t *= T)
                {
                    Comp nx = J[j + k], ny = t * J[i + j + k];
                    J[j + k] = nx + ny;
                    J[i + j + k] = nx - ny;
                }
            }
        }

        if (sign == -1)
        {
            for (int i = 0; i < LIM; ++i)
            {
                ans[i] = (int)(J[i].r / LIM + 0.5);
            }
        }
    }

    inline void work()
    {
        for (int i = 1; i < N; ++i)
        {
            A[i].r = d[i];
        }
        for (int i = 0; i < LIM; ++i)
        {
            R[i] = (R[i >> 1] >> 1) | (i & 1) << (L - 1);
        }

        fft(A, 1);
        for (int i = 0; i < LIM; ++i)
        {
            A[i] *= A[i];
        }
        fft(A, -1);
    }
} // namespace FFT

int main()
{
    prepare();
    FFT::work();

    using FFT::ans;

    int n;
    read(n);

    for (int cas = 0, l, r; cas < n; ++cas)
    {
        read(l), read(r);
        auto ptr = max_element(ans + l, ans + r + 1);
        printf("%d %d\n", (int)(ptr - ans), *ptr);
    }

    return 0;
}