Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Cặp số ngũ giác

Đếm các cặp số ngũ giác có tổng cũng là số ngũ giác.

Bạn sẽ học được gì

  • Sinh các số ngũ giác
  • Kiểm tra thuộc tập bằng công thức
  • Đếm cặp bằng hai vòng lặp lồng nhau

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.