2226: [Spoj 5971] LCMSum

Time Limit: 20 Sec  Memory Limit: 259 MB

Submit: 1123  Solved: 492

[][][]

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

思路：时间复杂度T*sqrt（n）；

　　　小于n并且与n互质的数为phi（k）*k/2；

　　　1的情况是特例；全部long long会超时。。。卡死我了

#include
      
       using namespace std;#define ll long long#define mod 1000000007#define inf 999999999#define esp 0.00000000001const int MAXN=1000010;int prime[MAXN],cnt;bool vis[MAXN];int phi[MAXN];void Prime(int n){    phi[1]=1;    for(int i=2;i