Đề bài
Số ngũ giác được tính theo công thức P(k) = k(3k − 1) / 2: 1, 5, 12, 22, 35, 51, 70, ... Có những cặp cộng lại ra một số ngũ giác khác, ví dụ P(4) + P(7) = 22 + 70 = 92 = P(8). Hãy đếm các cặp j < k ≤ n sao cho P(j) + P(k) là số ngũ giác. Có một cách kiểm tra nhanh: x là số ngũ giác khi và chỉ khi 24x + 1 là số chính phương s² với s % 6 = 5.
Hãy viết pentagonal_pair(n).
Đầu vào
n: Chỉ số k lớn nhất được dùng.
Đầu ra
Trả về số cặp (j, k) với 1 ≤ j < k ≤ n và P(j) + P(k) là số ngũ giác.
Ràng buộc
1 ≤ n ≤ 1000
Ví dụ
Đầu vào:
n = 7
Kết quả mong đợi:
expected = 1
Đầu vào:
long long n = 7;
Kết quả mong đợi:
long long expected = 1;
Đầu vào:
long n = 7;
Kết quả mong đợi:
long expected = 1;
Giải thích
Trong 21 cặp với k đến 7, chỉ có P(4) + P(7) = 92 = P(8) là số ngũ giác, nên đáp án là 1.
Đầu vào:
n = 1
Kết quả mong đợi:
expected = 0
Đầu vào:
long long n = 1;
Kết quả mong đợi:
long long expected = 0;
Đầu vào:
long n = 1;
Kết quả mong đợi:
long expected = 0;
Giải thích
Không có cặp nào với j < k ≤ 1, nên đáp án là 0.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
P(k) = k(3k − 1) / 2.
Gợi ý 2
Kiểm tra 24x + 1 có phải số chính phương bằng căn bậc hai nguyên, rồi kiểm tra căn theo modulo 6.
Gợi ý 3
Chỉ đếm các cặp có j < k.
Độ phức tạp mong đợi
thời gian O(n²), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.