COLTRI - Tam giác màu
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho điểm trên mặt phẳng, không có ba điểm nào thẳng hàng, các điểm được đánh số từ 1 đến ~n~. Người ta nối tất cả các cặp điểm ~(i, j)~ bằng sợi dây màu xanh hoặc màu vàng theo nguyên tắc: Nếu ~i + j~ là số nguyên tố thì điểm nối với điểm bằng sợi dây màu xanh, ngược lại nếu ~i + j~ không phải số nguyên tố thì nối bằng sợi dây màu vàng. Sau đó người ta muốn khảo sát xem có bao nhiêu hình tam giác mà ba đỉnh là 3 điểm trong ~n~ điểm được nối với nhau bằng các sợi dây cùng màu.
Yêu cầu: Cho ~n~, hãy đếm số hình tam giác mà ba đỉnh là 3 điểm trong ~n~ điểm được nối với nhau bằng các sợi dây cùng màu.
Input
- Dòng đầu tiên ghi số nguyên dương ~T (T ≤ 10)~ là số lượng bộ dữ liệu. Tiếp đến là ~T~ dòng, mỗi dòng tương ứng với một bộ dữ liệu chứa một số nguyên ~n~.
Giới hạn:
- Subtask 1: 30 tests có ~n \le 100~
- Subtask 2: 30 tests có ~n \le 1000~
- Subtask 3: 40 tests có ~n \le 10^6~
Output
- Gồm ~T~ dòng, mỗi dòng chứa một số nguyên là số tam giác đếm được tương ứng với bộ dữ liệu vào.
Sample
Input #1
2
3
5
Output #1
0
1
Problem source: Kc97ble - Free Contest 19
Bình luận
Vị cao nhân nào có thể gợi ý bài này cho tại hạ được không. Tại hạ thực lực non kém code trâu cắn được có 58/100 test.
bạn muốn tham khảo code mẫu ko
Bạn cứ up code đi. Mình sẽ đọc và chỉ nộp khi hiểu code của bạn. Nếu hiểu, xin phép được diễn giải bên dưới cho mọi người cùng hiểu, cảm ơn bạn trước
Có ạ
Bạn xem hộ mình Sub3 mình sai ở đâu đc ko ạ, Sub2 mình làm thì được 61/100 test ạ sub2_coltri