Input 1:

1

Output 1:

0

Explanation 1:

There are no satisfied integer pair $$$(a, b)$$$ that $$$1 \leq a < b \leq 1$$$

Input 2:

10

Output 2:

4

Explanation 2:

There are $$$4$$$ satisfied pairs: {$$$1, 4$$$}, {$$$1, 9$$$}, {$$$2, 8$$$}, {$$$4, 9$$$}.

Input 3:

25

Output 3:

16

Explanation 3:

There are $$$16$$$ satisfied pairs: {$$$1, 4$$$}, {$$$1, 9$$$}, {$$$1, 16$$$}, {$$$1, 25$$$}, {$$$2, 8$$$}, {$$$2, 18$$$}, {$$$3, 12$$$}, {$$$4, 9$$$}, {$$$4, 16$$$}, {$$$4, 25$$$}, {$$$5, 20$$$}, {$$$6, 24$$$}, {$$$8, 18$$$}, {$$$9, 16$$$}, {$$$9, 25$$$}, {$$$16, 25$$$}.

vector<int> prime; /// prime list
vector<int> lpf;   /// Lowest prime factor, lpf[x] is smallest prime divisor of x
void sieve(int lim = LIM) /// O(n)
{
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    lpf[1] = 1; /// For easier calculation but can cause inf loops
    for (int i = 3; i <= lim; i += 2) {
        if (lpf[i] == 2) prime.push_back(lpf[i] = i);
        for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
            lpf[prime[j] * i] = prime[j];
    }
}

/// mask(x) is smallest positive number that mask(x) * x is a perfect square
int getMask(int x) /// O(log n)
{
    int mask = 1;
    while (x > 1) {
        int p = lpf[x], f = 0;
        do x /= p, f++; while (p == lpf[x]);
        if (f & 1) mask *= p; /// if current power is odd, we mutiple mask with current prime
    }
    return mask;
}

int cnt[LIM];
int magic(int n) /// O(n log max(a))
{
    memset(cnt, 0, sizeof(cnt[0]) * (n + 1));

    ll res = 0;
    for (int a = 1; a <= n; ++a) /// Check all cases of a
        res += cnt[getMask(a)]++;

    res %= MOD;
    return res;
}

int main() /// O(n log max(a))
{
    int n;
    cin >> n;
    sieve(n + 500);
    cout << magic(n);    
    return 0;
}

int solve(int n)
{
    memset(is_squarefree, true, sizeof(is_squarefree[0]) * (n + 1));

    long long res = 0;
    for (int i = 1, j; i <= n; ++i) if (is_squarefree[i]) 
    {
        for (j = 1; i * j * j <= n; ++j)
            is_squarefree[i * j * j] = false;

        res += 1LL * (j - 1) * (j - 2) / 2;
    }

    res %= MOD;
    return res;
}

int solve(int n)
{
    memset(is_squarefree, true, sizeof(is_squarefree[0]) * (n + 1));

    long long res = 0;
    for (int i = 1; i <= n; ++i) if (is_squarefree[i]) 
    {
        for (int j = 1; i * j * j <= n; ++j)
        {
            is_squarefree[i * j * j] = false;
            res += j - 1;
        }
    }

    res %= MOD;
    return res;
}

/// Linear Sieve
vector<bool> isPrime; /// Characteristic function = A010051
vector<int> prime;    /// Prime list              = A000040
vector<int> lpf;      /// Lowest prime factor     = A020639
vector<int> mu;       /// Mobius                  = A008683
vector<int> phi;      /// Euler totient phi       = A000010
void sieve(int n)
{
    if (n < 1) return ;
    /// Extension part
    mu.assign(n + 1, 1);
    phi.assign(n + 1, 1);
    /// Main part
    prime.clear();
    lpf.assign(n + 1, 0);
    isPrime.assign(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int x = 2; x <= n; ++x)
    {
        if (isPrime[x]) /// Func[Prime]
        {
            lpf[x] = x;
             mu[x] = -1;
            phi[x] = x - 1;
            prime.push_back(x);
        }
 
        for (int p : prime) /// Func[Prime * X] <- Func[Prime]
        {
            if (p > lpf[x] || x * p > n) break;
            isPrime[x * p] = 0;
            lpf[x * p] = p;
            if (lpf[x] == p)
            {
                 mu[x * p] = 0;
                phi[x * p] = phi[x] * p;
            }
            else 
            {
                 mu[x * p] = -mu[x];
                phi[x * p] = phi[x] * phi[p];
            }
        }
    }
}

long long solve(int n)
{
    sieve(n + 1);
    long long res = 0;
    for (int x = 1; x <= n; ++x) if (mu[x]) 
    {
        int t = sqrt(n / x);
        res += 1LL * t * (t - 1) / 2;
    }

    res %= MOD;
    return res;
}

It just related to the sum of inversion of primes.

Precalculating smallest prime factor for each $$$n$$$.

Since you known the smallest prime factor for each $$$n$$$, you can factorize any number in $$$O(\log n)$$$.

There are $$$n$$$ number total. Hence the calculating part take $$$O(n \log n)$$$.

The sieve only cost you $$$O(n)$$$ give the total complexity of $$$O(n \log n)$$$.

This just a clickbait. Have a nice day.

Each number will be calculated once.

Though some numbers might be visited many times. It is actually armotized to constant.

Let remind you about something called the sum of inversion of squares.

Just ignore those squarefree. A normal loop through it is still linear.

$$$O\left(\underset{\text{squarefree } p \leq n}{\Large \Sigma} \left \lfloor {\Large \frac{n}{p^2}} \right \rfloor \right) = O\left(\underset{p \leq n}{\Large \Sigma} {\Large \frac{n}{p^2}} \right) = O\left(n \times {\Large \Sigma} {\Large \frac{1}{p^2}} \right) = O\left(n \times {\Large \frac{\pi^2}{6}} \right) = O(n)$$$.

It depends on the sieve as the calculation is already linear.

Each number can be represent as $$$x = lpf[x] \times k$$$ where $$$lpf[x]$$$ is lowest prime factor of $$$x$$$ and $$$k$$$ is an integer

Each $$$x$$$ can be represented uniquely as the form $$$x = lpf[x] \times k$$$.

So you can make a sieve of linear, where each number is visisted once or atmost $$$O(1)$$$

Input 1:

2 1

Output 1:

2

Explanation 1:

There are $$$2$$$ satisfied array of size $$$1$$$: {$$$1$$$}, {$$$2$$$}.

Input 2:

10 2

Output 2:

4

Explanation 2:

There are $$$4$$$ satisfied array of size $$$2$$$: {$$$1, 4$$$}, {$$$1, 9$$$}, {$$$2, 8$$$}, {$$$4, 9$$$}.

Input 3:

27 3

Output 3:

12

Explanation 3:

There are $$$12$$$ satisfied array of size $$$3$$$: {$$$1, 4, 9$$$}, {$$$1, 4, 16$$$}, {$$$1, 4, 25$$$}, {$$$1, 9, 16$$$}, {$$$1, 9, 25$$$}, {$$$1, 16, 25$$$}, {$$$2, 8, 18$$$}, {$$$3, 12, 27$$$}, {$$$4, 9, 16$$$}, {$$$4, 9, 25$$$}, {$$$4, 16, 25$$$}, {$$$9, 16, 25$$$}.

const int LIM = 1e7 + 17;
const int MOD = 1e9 + 7;

int fact[LIM + 1]; /// factorial:         fact[n] = n!
int invs[LIM + 1]; /// inverse modular:   invs[n] = n^(-1)
int tcaf[LIM + 1]; /// inverse factorial: tcaf[n] = (n!)^(-1)
void precal_nck(int n = LIM)
{
    fact[0] = fact[1] = 1;
    invs[0] = invs[1] = 1;
    tcaf[0] = tcaf[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
        invs[i] = MOD - 1LL * (MOD / i) * invs[MOD % i] % MOD;
        tcaf[i] = (1LL * tcaf[i - 1] * invs[i]) % MOD;
    }
}

int nck(int n, int k)
{
    k = min(k, n - k);
    if (k < 0) return 0;

    long long res = fact[n];
    res *= tcaf[k];         res %= MOD;
    res *= tcaf[n - k];     res %= MOD;
    return res;
}

int solve(int n, int k)
{
    memset(is_squarefree, true, sizeof(is_squarefree[0]) * (n + 1));
    precal_nck(n);

    long long res = 0;
    for (int i = 1, j; i <= n; ++i) if (is_squarefree[i]) 
    {
        for (j = 1; i * j * j <= n; ++j)
            is_squarefree[i * j * j] = false;

        res += nck(j - 1, k);
    }

    res %= MOD;
    return res;
}