题目描述

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

题目分析

题目要我们求







快筛欧拉函数+预处理

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,t;
long long prime[1000100],phi[1000100];
long long f[1000100];
bool vis[1000100];
void init()
{
    for(int i=2;i<=1000000;i++)
    {
        if(!vis[i]) prime[++prime[0]]=i,phi[i]=i-1;
        for(int j=1;j<=prime[0]&&i*prime[j]<=1000000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) 
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=2;i<=1000000;i++)
        for(int j=i;j<=1000000;j+=i)
            f[j]+=(long long) (phi[i]*i)/2;
}
int main()
{   
    init();
    scanf("%d",&t);
    for(int i=1;i<=t;i++) 
        scanf("%d",&n),printf("%lld\n",(f[n]+1)*n);
    return 0;
}