Tổng GCD

View as PDF

Submit solution


Points: 180
Time limit: 1.0s
Python 3 3.5s
Scratch 18.0s
Memory limit: 100M
Python 3 512M
Scratch 900M

Author:
Problem types
Allowed languages
Awk, C++, Pascal, Python, Scratch

Cho số nguyên dương \(N\).
Tính giá trị biểu thức: \[\sum\limits_{i = 1}^{N} {GCD(N,{i^2})}\]
Nói cách khác, bạn hãy tính giá trị của biểu thức \(GCD(N,1^2) + GCD(N, 2^2) + .... + GCD(N,N^2)\).
Trong đó, \(GCD(a,b)\) chính là ước chung lớn nhất của \(a\) và \(b\).

Định nghĩa: Ước chung lớn nhất của hai số \(a\) và \(b\) là số nguyên dương lớn nhất mà cả \(a\) và \(b\) đều chia hết.

Dữ liệu:

  • Dòng đầu ghi \(q\) \((q \le 75)\) - số câu hỏi.
  • \(q\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(N\) \((N \le 10^5)\).

Kết quả:

  • Ứng với mỗi testcase, in ra đáp án cần tìm.

Sample input

1
2
3
2
1
2

Sample Output

1
2
1
3

Giải thích:

  • \(GCD(1,1) = 1\)
  • \(GCD(2,1) + GCD(2,4) = 1 + 2 = 3\)