Giả sử chúng ta có hai giá trị p và q, chúng ta phải tìm số ô vuông duy nhất có thể được tạo ra từ một lưới có p hàng và q cột trong đó các điểm được đặt cách đều nhau. Nếu câu trả lời là rất lớn, kết quả trả về mod 10 ^ 9 + 7. Trong bài toán này, hình vuông là tập hợp 4 điểm tạo thành bốn đỉnh của hình vuông. Các cạnh của hình vuông phải có cùng độ dài và không phải lúc nào nó cũng cần phải được căn chỉnh với các trục của lưới.
Vì vậy, nếu đầu vào là p =4, q =4, thì đầu ra sẽ là 20.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
đối với tôi trong phạm vi tối thiểu từ r đến c, làm,
-
ans:=ans + (r - i) * (c - i) * i
-
return ans mod (10 ^ 9 + 7)
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution: def solve(self, r, c): ans = 0 for i in range(min(r, c)): ans += (r - i) * (c - i) * i return ans % (10 ** 9 + 7) ob = Solution() print(ob.solve(4,4))
Đầu vào
p = 4 q = 4
Đầu ra
20