APS2 - Amazing Prime Sequence (hard)
题意翻译
共 $T$ 组数据。
询问 $1,\ldots,n$ 的正整数的最小质因子之和对 $2^{64}$ 取模的结果。
题目描述
This problem is a harder version of [APS](../APS).
Let $ f(n) $ be the smallest prime factor of $ n $ . For example, $ f(2) = 2,\ f(4) = 2 $ and $ f(35) = 5 $ .
The sequence $ S(n) $ is defined for all positive integers as follows:
\- $ S(1) = 0 $
\- $ S(n) = S(n-1) + f(n) $ (if $ n \ge 2 $ )
Given $ N $ , find $ S(N) $ **modulo** $ 2^{64} $ .
输入输出格式
输入格式
First line contains $ T $ ( $ 1 \le T \le 10000 $ ), the number of test cases.
Each of the next $ T $ lines contains a single integer $ N $ . ( $ 1 \le N \le 1234567891011 $ )
输出格式
For each integer $ N $ , output a single line containing $ S(N) $ **modulo** $ 2^{64} $ .
输入输出样例
输入样例 #1
5
1
4
100
1000000
1000000000000
输出样例 #1
0
7
1257
37568404989
7294954823202325427