GCDSUM

Xem PDF
Thời gian:
Python 3 3.5s
Scratch 18.0s
Bộ nhớ:
Python 3 512M
Scratch 900M
Tác giả:
dang7rickroll
Dạng bài
Ngôn ngữ cho phép
Awk, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 180 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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.

Input

  • 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)\).

Output

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

Example

Test 1

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

Bình luận


  • 5
    dang7rickroll    6:27 p.m. 27 Tháng 11, 2021 ← đã chỉnh sửa

    Thấy mấy bạn làm Python TLE nhiều quá :vvvv mình mới thêm pascal với C++ rồi nha. Các bạn vào submit lại đi

    P/s: Mình đã xóa bớt comment đi để cho gọn phần comment rồi nhé.

    • 5 bình luận nữa