Tính tổng với GCD

View as PDF

Points: 2300 Time limit: 5.0s Memory limit: 977M Input: stdin Output: stdout

Cho số nguyên dương \(n\). Tính \(S=\sum\limits_{i=1}^{n}gcd(\left \lfloor{\sqrt[3]{i}}\right \rfloor ,i)\)

Trong đó:

  • \(gcd(a,b)\) - Thể hiện ước chung lớn nhất của hai số nguyên dương \(a\)\(b\)

  • \(\left \lfloor{x}\right \rfloor\) - Thể hiện số nguyên lớn nhất và không vượt quá \(x\) (với \(x\) nguyên)

Input

  • Dòng thứ nhất chứa số \(t(1\le t\le 10)\) - Thể hiện số testcase

  • \(t\) dòng tiếp theo, mỗi dòng chứa số \(n(1\le n\le 10^{21})\)

Output

  • Ứng với mỗi testcase, in ra \(S\) cần tìm. Vì \(S\) có thể rất lớn, nên ta cần lấy mod \(998244353\) trước khi in ra (Biết rằng: \(998244353\) là số nguyên tố.)

Scoring

  • \(10\%\) : \(1\le n\le 100\)

  • \(10\%\) : \(1\le n\le 1000000\)

  • \(20\%\) : \(1\le n\le 10^{9}\)

  • \(30\%\) : \(1\le n\le 10^{16}\)

  • \(30\%\) : Không có điều kiện gì

Example

Test 1

Input
3
180
526
267
Output
327
1069
522

Comments

There are no comments at the moment.