Description

Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.

Input

The first line contains T the number of test cases. Each of the next T lines contain an integer n.

Output

Output T lines, one for each test case, containing the required sum.

Sample Input

3
1
2
5

Sample Output

1
4
55

HINT

Constraints

1 <= T <= 300000
1 <= n <= 1000000

题意简述

i=1nlcm(i,n)\sum_{i=1}^{n} \; lcm(i,n)

题意简述$\sum_{i=1}^{n} \; lcm(i,n)$ $\sum\limits_{d|n}\sum\limits_{i=1}^{n}[gcd(i,n)==d]\frac{i*n}{d}$ $n*\sum\limits_{d|n}\sum\limits_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})==1]*i$ $n*\sum\limits_{d|n}\sum\limits_{i=1}^{d}[gcd(i,d)==1]*i$ 那么最后这个式子就是求得是1~i中与i互质的数的和 这个和等于$\varphi(n)*n/2$ 证明大概如下:$gcd(i,n)=1$必有$gcd(n-i,n)=1$于是可以通过对称的方式推导出 因为i和n-i均成对出现 想试着自己写粗来 推来推去 最后的几步还是没推导出 详细证明:https://blog.csdn.net/clover_hxy/article/details/53152358

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论