LCMSUM - LCM Sum

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.

Example

```Sample Input:
3
1
2
5

Sample Output:
1
4
55```

Constraints

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

Code Examples

#1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define MOD (ll)1000000007
#define pb 	push_back
#define EPS 1e-9
// #define FOR(i, n)	for(int i = 0;i < n; i++)
#define pi(a)   printf("%d\n", a)
#define all(c)  c.begin(), c.end()
#define tr(container, it)   for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define FOR(i, a, b)	for(int i = (a); i  < = (b) ; i++)

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}

const int MAXN = (int)1e6;
ll phi[MAXN+1];
ll res[MAXN+1];
void precal(){
for(int i = 1;i <= MAXN; i++){
phi[i] = i;
}
for(int i = 2;i <= MAXN; i++){
if(phi[i] == i){
for(int j = i; j <= MAXN; j+=i){
phi[j]/=i;
phi[j]*=(i-1);
}
}
}
for(int i = 1;i <= MAXN; i++){
for(int j = i; j <= MAXN; j+=i){
res[j] += (i*phi[i]);
}
}

}

int main(){
precal();
int t;
si(t);
while(t--){
int n;
si(n);
ll ans = res[n]+1;
ans*=n;
ans/=2;
printf("%lld\n", ans);
}
return 0;
}``````
Copy The Code &

Input

cmd
3
1
2
5

Output

cmd
1
4
55

#2 Code Example with Java Programming

```Code - Java Programming```

``````import java.lang.StringBuilder;
import java.io.DataInputStream;
import java.io.IOException;

final private int BUFFER_SIZE = 1 << 16;
private DataInputStream dis;
private byte[] buffer;

dis = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
}

public void omitLines(int n) throws IOException{
while (n > 0){
n--;
}
}

public int nextInt() throws IOException{
int ret = 0;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do{
ret = ret * 10 + c - '0';
}  while ((c = read()) >= '0' && c <= '9');

if (neg)
return -ret;
return ret;
}

public long nextPositiveLong() throws IOException{
long ret = 0;
while (c <= ' ')
do{
ret = ret * 10 + c - '0';
}  while ((c = read()) >= '0' && c <= '9');

return ret;
}

public int nextPositiveInt() throws IOException{
int ret = 0;
while (c <= ' ')
do{
ret = ret * 10 + c - '0';
}  while ((c = read()) >= '0' && c <= '9');

return ret;
}

private void fillBuffer() throws IOException{
buffer[0] = -1;
}

fillBuffer();
return buffer[bufferPointer++];
}

public void close() throws IOException{
if (dis == null)
return;
dis.close();
}
}

final class LCMSUM{
final static int [] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};

public static void main(String args[]) throws IOException{
StringBuilder sb = new StringBuilder();
int T = r.nextPositiveInt(), n;
int MAX_N = 1000000;

int [] PHI = new int [MAX_N + 1];

PHI[1] = 1;

for (int i = 2; i <= MAX_N; i++){
if (PHI[i] == 0){
PHI[i] = i - 1;
for (int j = (i << 1); j <= MAX_N; j += i){
if (PHI[j] == 0){
PHI[j] = j;
}
PHI[j] = (PHI[j]/i)*(i - 1);
}
}
}

long [] L = new long [MAX_N + 1];
for (int i = 1; i <= MAX_N; i++){
for (int j = i; j <= MAX_N; j += i){
L[j] += (long)i*PHI[i];
}
L[i] = (L[i] + 1)*i/2;
}

while (T-- > 0){
n = r.nextPositiveInt();
sb.append(L[n]);
sb.append('\n');
}

System.out.print(sb.toString());
}
}``````
Copy The Code &

Input

cmd
3
1
2
5

Output

cmd
1
4
55