VNOJ Round 01 - GCD
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một số nguyên dương ~n~, hãy đếm số cặp ~(x, y)~ mà:
~1 \le x \le y \le n~.
~\gcd(x, n)\times\gcd(y, n)=\gcd(x\times y, n)~.
Với hàm ~\gcd(x, y)~ là ước chung lớn nhất của ~x, y~.
Input
Dòng đầu chứa số nguyên dương ~T~ (~1\le T \le 10^5~) thể hiện số lượng test.
~T~ dòng tiếp theo mỗi dòng chứa một số nguyên dương ~n~ (~1\le n \le 10^5~).
Output
- ~T~ dòng mỗi dòng in ra một số nguyên dương duy nhất là kết quả của test tương ứng.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~30~ | ~1\le T \le 50, 1\le n \le 500~ |
| 2 | ~70~ | Không có ràng buộc gì thêm |
Sample Input 1
2
3
4
Sample Output 1
5
8
Notes
Ở test ví dụ thứ 1: có các cặp ~(x,y)~ thỏa mãn là: ~(1,1),(1,2),(1,3),(2,2),(2,3)~.
Ở test ví dụ thứ 2: có các cặp ~(x,y)~ thỏa mãn là: ~(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,3),(3,4)~.
Bình luận
Ủa tôi thấy ở test ví dụ thứ 2 cặp (x, y) = (2, 4) và (4, 4) vẫn thỏa đề bài mà đúng không?
sao thỏa được bạn? với (x,y) = (2,4) thì gcd(2,4) x gcd(4,4) = 2 x 4 = 8 trong khi gcd(2x4,4) = 4 mà. Tương tự gcd(4,4) x gcd(4,4) = 4 x 4 = 16 trong khi gcd(4x4,4) = 4 thôi bạn.
mọi người biết cách giải không