Tính tổng với GCD
Xem PDF
Điểm:
2300
Thời gian:
5.0s
Bộ nhớ:
977M
Input:
bàn phím
Output:
màn hình
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\) và \(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
267Output
327
1069
522
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Về việc tính tổng S2 thì có thể dùng Multiple Mobius Transform để rút đpt xuống \(O(n^{1/6}+d(n^{1/3})*log(n))\). Để tính truớc hàm Phi và biểu thức Q có thể dùng sàng tuyến tính (cách này chạy 340ms ở max test). Đpt: \(O(\sqrt[3]{n}+t(\sqrt[6]{n}+d(\sqrt[3]{n})*log(n)))\)