Hướng giải của Mật mã điều hòa
Hướng dẫn giải
Read the intended approach and key ideas behind this problem.
Hãy nhớ chỉ sử dụng editorial này khi thật sự bị bí, và tuyệt đối không sao chép–dán code từ đó. Hãy tôn trọng tác giả bài toán và người viết lời giải.
Nộp lời giải chính thức trước khi tự mình giải được bài là hành vi có thể bị cấm (ban).
Nộp lời giải chính thức trước khi tự mình giải được bài là hành vi có thể bị cấm (ban).
Tác giả:
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;
Không có ý kiến tại thời điểm này.