Đếm hình vuông (THT TQ 2013)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Điểm: 200 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bài 1 THT bảng B, năm 2013

Cho một bảng hình vuông kích thước \(n \times n\) được chia thành lưới ô vuông đơn vị, các vị trí
đỉnh của các ô vuông đơn vị được gọi là các mắt lưới. Người ta muốn đếm số lượng những hình
vuông thỏa mãn hai điều kiện sau:

  • Mỗi cạnh hình vuông phải song song với một trong hai cạnh bảng.
  • Cả 4 đỉnh của hình vuông phải nằm tại vị trí của các mắt lưới.

Ví dụ với bảng kích thước \(3 \times 3\) ta có thể đếm được \(14\) hình vuông thỏa mãn hai điều kiện
trên.

Vì số lượng hình vuông đếm được có thể rất lớn nên em chỉ cần cho biết kết quả là số dư của
phép chia: số lượng hình vuông đếm được chia cho \(2013\).

Input

Số nguyên dương \(n (n \le 10^{18})\)

Output

Số lượng hình vuông tìm được \(\mod 2013\).

Bình luận