Nội dung Bài tập
- Mã:
- SQCOUNT
- Tên:
- Đếm hình vuông
- Dạng thi:
- acm
- Thang điểm:
- 1 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 64 MB
- Được tạo bởi:
- nxphuc
Cho một mặt phẳng gồm N*M điểm, gồm N dòng, mỗi dòng M điểm.
Quảng cáo
Hỏi có bao nhiêu cách tạo thành 1 hình vuông bằng cách sử dụng các điểm trên mặt phẳng. Hai hình vuông được gọi là khác nhau nếu kích thước của chúng là khác nhau, hoặc tập tọa độ các điểm là khác nhau.
Số cách chọn có thể rất lớn, vì vậy chỉ cần xuất ra phần dư sau khi chia cho 1000000007 (109+7)
Input:
- Dòng đầu tiên chứa số nguyên T là số lượng test case cần kiểm tra (T ≤ 100).
- T dòng tiếp theo, mỗi dòng gồm 2 số N, M là kích thước của mặt phẳng (2 ≤ N, M ≤ 109).
Output:
- Gồm T dòng, mỗi dòng chứa một số nguyên duy nhất là kết quả cần tìm của test case tương ứng.
Ví dụ:
Input:
4
2 4
3 4
4 4
1000 500
Output:
3
10
20
624937395
Bên dưới là hình ảnh minh họa mặt phẳng của 3 test case đầu tiên. Riêng ở hình 3 có kèm theo minh hoạt 1 cách đặt hình vuông hợp lệ.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...