VNOJ Round 01 - GCD

View as PDF

Submit solution


Points: 0.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
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)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.