GCDEX2 - GCD Extreme (hard)
题意翻译
给定 $n$ ($1\le n\le 235711131719$),计算
$$G(n)=\sum_{i=1}^n\sum_{j=i+1}^n\gcd(i,j)$$
答案对 $2^{64}$ 取模。
有多组询问 $(T\le10^4)$。
题目描述
This problem is a harder version of [GCDEX](../GCDEX).
Let
$$ G(n) = \sum _{i=1}^{n} \sum _{j=i+1}^{n} \gcd(i, j). $$
For example, $ G(1) = 0 $ , $ G(2) = \gcd(1, 2) = 1 $ , $ G(3) = \gcd(1, 2) + \gcd(1, 3) + \gcd(2, 3) = 3 $ .
Given $ N $ , find $ G(N) $ **modulo** $ 2^{64} $ .
输入输出格式
输入格式
First line of 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 235711131719 $ )
输出格式
For each number $ N $ , output a single line containing $ G(N) $ **modulo** $ 2^{64} $ .
输入输出样例
输入样例 #1
5
1
4
100
1000000
100000000000
输出样例 #1
0
7
13015
4071628673912
5482289417216306300