Algorithm
problem link- https://www.spoj.com/problems/LCMSUM/
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;
}Input
3
1
2
5
1
2
5
Output
1
4
55
4
55
#2 Code Example with Java Programming
Code -
Java Programming
import java.lang.StringBuilder;
import java.io.DataInputStream;
import java.io.IOException;
final class Reader{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream dis;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader(){
dis = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public void omitLines(int n) throws IOException{
while (n > 0){
if (read() == '\n')
n--;
}
}
public int nextInt() throws IOException{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
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;
byte c = read();
while (c <= ' ')
c = read();
do{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return ret;
}
public int nextPositiveInt() throws IOException{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
do{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return ret;
}
private void fillBuffer() throws IOException{
bytesRead = dis.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException{
if (bufferPointer == bytesRead)
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{
Reader r = new Reader();
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());
}
}Input
3
1
2
5
1
2
5
Output
1
4
55
4
55
Demonstration
SPOJ Solution-LCM Sum-Solution in C, C++, Java, Python