Subtask 1

Duyệt toàn bộ cặp ~1 \le i < j \le n~ và kiểm tra 2 điều kiện: ~i \times j \le m~ và ~i \times j~ là số chính phương.

Độ phức tạp: ~\mathcal{O}(n^2)~

Subtask 2

Nhận thấy ~i \le \sqrt{m}~. Với mỗi ~i~, ta duyệt ~j~ từ ~i+1~ đến ~\min(n,m/i)~. Với mỗi cặp ~(i,j)~ ta chỉ cần kiểm tra điều kiện ~i \times j~ có phải số chính phương hay không.

Độ phức tạp: ~\mathcal{O}(m\log m)~

Subtask 3

Với mỗi số ~i~, ta gọi ~p[i] = i / x~ với ~x~ là số chính phương lớn nhất mà ~i~ chia hết. Ta có thể tính được ~p[i]~ bằng cách phân tích thừa số nguyên tố của số ~i~ ra và đặt ~p[i] = ~ tích các ước nguyên tố có lũy thừa lẻ. Khi đó chi phí chuẩn bị mảng ~p~ là ~\mathcal{O}(n\log n)~

Nhận xét: tích hai số ~i~ và ~j~ là số chính phương khi và chỉ khi ~p[i] = p[j]~. Với mỗi ~j~, ta sẽ đếm số lượng ~i < j~ mà ~p[i]=p[j]~ và ~i \times j \le m~. Ta có thể làm việc này bằng hai con trỏ, chi phí là ~\mathcal{O}(n)~.

Độ phức tạp: ~\mathcal{O}(n \log n)~

Subtask 4

Ta sẽ dựng mảng ~p~ nhanh hơn như sau:

for (int i = 1; i <= n; i++) 
    p[i] = i;
for (int i = 2; i*i <= n; i++) {
    for (int j = i*i; j <= n; j += i*i)
        p[j] = j / (i*i);
}

Với cách này chi phí xây dựng mảng ~p~ sẽ là ~\mathcal{O}(n)~.

Độ phức tạp: ~\mathcal{O}(n)~

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 1E7;

int f[N+9];
int p[N+9];
int n;
ll m;
ll ans = 0;

int main()
{
    if (fopen(name".INP","r"))
        freopen(name".INP","r",stdin),
        freopen(name".OUT","w",stdout);

    fastIO

    cin>>n>>m;

    for (int i = 1;i <= n; ++i) p[i] = i;

    for (int i = 2;i*i <= n; ++i)
        for (int j = i * i;j <= n; j += i * i)
            p[j] = j / (i*i);

    for (int i = 1;i <= n; ++i) f[p[i]]++;

    for (int R = n, L = 1; L <= R;)
    {
        if (1LL * L * R <= m)
        {
            ans += (f[p[L]] - 1);
            --f[p[L]];
            ++L;
        }
        else
        {
            --f[p[R]];
            --R;
        }
    }

    cout<<ans;
}