Tóm tắt đề bài: bạn được cho một mảng A gồm N phần tử. Một đoạn "tốt" là một dãy các phần tử liên tiếp có tích biểu diễn được dưới dạng hiệu của hai số chính phương. Đếm số lượng đoạn "tốt" trong mảng A.
Khái niệm "đoạn con" sử dụng trong bài được định nghĩa là dãy các phần tử liên tiếp. Một phần tử cũng được tính là một đoạn con.
Hướng dẫn giải: Để một số có thể biểu diễn dưới dạng hiệu của hai số chính phương thì số đó phải là số lẻ hoặc là bội của 4 (để tập trung vào giải thuật, phần chứng minh các bạn đọc thêm trên MathExchange: chứng minh một số lẻ bất kỳ có thể được biểu diễn dưới dạng hiệu của hai số chính phương và chứng minh một số là bội của 4 có thể biểu diễn dưới dạng hiệu của hai số chính phương). Trái lại, một số chẵn mà không chia hết cho 4 sẽ không thể biểu diễn dưới dạng hiệu của hai số chính phương.
(*) Từ phần xanh lá, ta có thể đưa bài toán về bài toán "đếm số lượng đoạn không thể biểu diễn dưới dạng hiệu của hai số chính phương (U)", sau đó dùng tổng số lượng đoạn con có thể tạo trừ đi U sẽ thu được kết quả cần tìm.
Tổng quát: số lượng đoạn con có thể tạo từ một dãy N phần tử là }{2} "\frac{N(N+1)}{2}")
.
Để một đoạn con có tích chia hết cho 2 nhưng không chia hết cho 4, ta chỉ cần xác định vị trí của các phần tử mà biểu diễn dưới dạng tích các số nguyên tố của nó chỉ có 1 số 2 duy nhất, gọi là số neo. 1 số chẵn nhân với 1 số lẻ ra một số chẵn, mà số chẵn ban đầu không chia hết cho 4 dẫn đến kết quả sau khi nhân số lẻ cũng sẽ không chia hết cho 4. Do vậy, công việc của ta là đếm số lượng số lẻ ở 2 bên của số neo, tính tổng số lượng đoạn con có thể tạo thành.
Cần chú ý là nếu 2 bên của số neo không có số lẻ nào thì độ dài dãy đó bằng 1. Làm theo (*) là ta có được kết quả đề bài.
CU;WTF?: tìm trong mảng A những số chia hết cho 2 mà không chia hết cho 4. Với mỗi số đó, đếm xem bên trái có bao nhiêu số lẻ, bên phải có bao nhiêu số lẻ, cộng 2 cái đó lại, cộng thêm 1 là số 2 đứng giữa. Tính theo công thức là tìm được tổng số đoạn con dạng U. Lặp lại đến hết mảng A, rồi lấy tổng số đoạn con của mảng A trừ tổng số đoạn con dạng U là ra kết quả.
Bài này không khó nhưng cài thuật ad-hoc rất khó.
No comments:
Post a Comment