goldenAreas

Chị Đại có đứa em trai tên Mười. Một hôm hai chị em rủ nhau đi đào vàng. Khu vực hai chị em đi đào là một mảnh vườn có kích thước NxN. Ở mỗi ô trên mảnh vườn sẽ có một con số bí ẩn, ô (i,j) có con số A[i,j]. Xét ô (i,j) và 5 ô lân cận như bản đồ bên dưới, cụ thể ô (i,j) có giá trị a, ô (i,j+1) có giá trị b, ô (i+1,j) có giá trị c, … Truyền thuyết kể lại rằng một ô có vị trí (i,j) sẽ chứa vàng nếu như tồn tại duy nhất một bộ số (x,y) sao cho ax+by = p và cx+dy = q. Như bản đồ thì Đại và Mười chỉ xét các ô từ hàng 1->N-1 và cột từ 1->N-2.

Chị Đại và bé Mười muốn biết có bao nhiêu ô có chứa vàng để hai chị em đào.

Ví dụ:

• Với A = [[1,2],[3,4]], (hình minh hoạ), kết quả là goldenAreas(A) = 0 vì không thể xét được ô nào
• Với A = [[1,2,3],[1,2,6],[2,3,5]], (hình minh hoạ), kết quả là goldenAreas(A) = 1 . Các ô được xem xét là A(1,1) = 1 và A(2,1) = 1. Ô (1,1) không tồn tại bộ (x,y) nào để x+2y = 3 và x+2y = 6, do đó ô này không có vàng. Ô (2,1) tồn tại bộ (x=-8; y=7) thoả x+2y=6 , 2x+3y=5.

Đầu vào/đầu ra:

• [Thời gian chạy] 0.2 giây với C++, 1.2 giây với Java và C#, 1.6 giây vs Python và Js
• [Đầu vào] matrix.integers A
  A là ma trận vuông
  1 <= A.size() <= 50
-100 <= A[i][j] <= 100
• [Đầu ra] integer
  Số ô có vàng cần tìm.