Yêu cầu bài toán: In ra số cặp ~(i,j),i<j~ sao cho ~lcm(a_i,a_j )*gcd⁡(a_i,a_j)~ có đúng 3 ước số.

Nhận xét 1: ~lcm(a_i,a_j )gcd⁡(a_i,a_j )=a_ia_j~.

Nhận xét 2: Số có đúng 3 ước số là số chính phương và căn bậc hai của số đó là một số nguyên tố.

Nhận xét 3: Số cặp (i,j) thỏa mãn yêu cầu bài toán là số lượng các số nguyên tố bằng nhau cộng với số lượng số 1 nhân với số lượng a[i] chính phương mà √(a[i]) là số nguyên tố.

Như vậy để tạo ra ~a_i*a_j~ là số có 3 ước số thì có 2 trường hợp

TH1: ~a_i=a_j~ và ~a_i,a_j~ là các số nguyên tố.

TH2: a_i=1, và a_j là số chính phương, √(a_j ) là số nguyên tố.

Từ đó ta có giải thuật như sau:

Bước 1: Sàng nguyên tố để đánh dấu mảng nguyên tố.

Bước 2: Xây dựng mảng đếm số lượng số nguyên tố d[] trong mảng a.

Bước 3: Tính tổng số lượng các số nguyên tố bằng nhau.

Bước 4: Đếm x số lượng số 1 và y là số lượng số có đúng 3 ước số; lấy x*y là số cặp tạo nên tích a_i*a_j là số có đúng 3 ước số.

Kết quả là tổng của cả hai số lượng trên.

Mã:

for(int i=1;i<=n;i++)
{
    if(nt[a[i]])// trường hợp 1 có các số ai, aj bằng nhau và là nguyên tố
    {
        s = s + d[a[i]];
        d[a[i]]++;
    }

    if(a[i]==1) x++;//trường hợp 2 có ai = 1, aj là số có đúng 3 ước.
    long long k = sqrt(a[i]);
    if(k*k==a[i] && nt[k]) y++;
}
s = s + x*y;