# One more GCD sum

Mathematics

Hard

### Problem Statement (Simplified):

Calculate the sum for a given number n:

$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\frac{i*j}{gcd(i,j)^{2}}$

See original problem statement here

### Solving Approach :

Bruteforce Approach:

1) We can use a double loop to count sum for a given value of n, where a loop also occurs inside two loops to find gcd(i,j).
2) The Above approach use three loops to solve the given problem. So it takes a total of O(n³) time complexity which is highly inefficient for given constraints, so we add some maths magic to it and solve it faster.

Efficient Approach:

1) Let gcd(i,j) = d, where d can go from 1 to n. If gcd(i,j) is d, i and j can be represented as some multiple of d, let i=k*d and j=l*d, where k<l because i 2) Our summation equation is $\frac{i*j}{gcd(i,j)^{2}}$, from above step we can see it becomes,

=> $\frac{k*d*l*d}{gcd(i,j)^{2}}$ (i=k*d and j=l*d)

=> $\frac{k*d*l*d}{d^{2}}$ (gcd(i,j) = d)

=> k*l

3) Now, we have one summation for one value of d ranging from 1 to N, internally we have (k*l) summation over all pairs where l>k and gcd(l,k)=1. Total number of pairs such that gcd(n,k)=1 where k lies between 1 and n can be found by using Euler Totient Function. An array phi will be maintained for such values.
4) Also we know gcd(l,k) = gcd(l,l-k) where l>k and l>l-k, so in above recieved equation we can change value of k to l-k, as they both will have same gcd(), so sum(k*l) = sum(l*(l-k))).
5) We can make it further easy, as sum(kl) = sum($\frac{l^{2}}{2})$ which is also equal to $sum(l^{2}*phi(l)/2)$ because we still need to find summation over gcd(l,k)=1, where k
6) Now we have only l as variable to cound ranging from 2 to ($\frac{n}{d}$) and d lies in range 1 to n, which can be find in O($n\times {log(n)}$) time for a given value of n.
7) However we can calculate for all n = 2 to 2000000 using the below pseudocode:

Calculate phi() for all values between 1 to max range of numbers.
phi(n) returns the total number of values from 1 to n which have gcd() with n as 1.

Calculate (l*l*phi(l))/2 for all values of 2 to n with double summation as asked in the problem.

8) Note: Don’t forget to take modulo to avoid overflow.

### Example

• Lets assume N to be 10, the phi table for it would be:
N 1 2 3 4 5 6 7 8 9 10
Value 1 1 2 2 4 2 7 2 6 4
• Where, phi(8) will be 2 because, 3 and 5 both have gcd() 1 with 8.

• Now , we have found the value of phi(k).

• We find sunmmation of all values from 1 to 10 with derived formula.

• Hence resultant array would be:

N 1 2 3 4 5 6 7 8 9 10
Value 0 2 11 29 79 126 273 419 671 923
• Hence, gcd sum of 10 will be 923.

### Solutions

#include <stdio.h>
#define ll long long
#define N 1000000007
#define maxn 2000001

ll phi[maxn];
ll res[maxn];

void pre()
{
ll i,j;
for(i=1;i<maxn;i++)
phi[i] = i;
for(i=2;i<maxn;i++)
{
if(phi[i] == i)
{
for(j=i;j<maxn;j=j+i)
{
phi[j] = (phi[j]/i)*(i-1);
}
}
}
for(i=2;i<maxn;i++)
for(j=i;j<maxn;j=j+i)
res[j] = (res[j] + (((i*i)%N)*((phi[i]*500000004)%N))%N)%N;

for(i=2;i<maxn;i++)
res[i] = (res[i] + res[i-1])%N;
}

int main() {

pre();
int test;
scanf("%d",&test);

while(test--){
int n;
scanf("%d",&n);
ll ans =     res[n];
ans = (ans+N)%N;
printf("%d\n",ans);
}
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000000007
#define maxn 2000001

ll phi[maxn];
ll res[maxn];

void pre()
{
ll i,j;
for(i=1;i<maxn;i++)
phi[i] = i;
for(i=2;i<maxn;i++)
{
if(phi[i] == i)
{
for(j=i;j<maxn;j=j+i)
{
phi[j] = (phi[j]/i)*(i-1);
}
}
}
for(i=2;i<maxn;i++)
for(j=i;j<maxn;j=j+i)
res[j] = (res[j] + (((i*i)%N)*((phi[i]*500000004)%N))%N)%N;

for(i=2;i<maxn;i++)
res[i] = (res[i] + res[i-1])%N;
}

int main() {

pre();
int test;
cin>test;

int v[maxn] = {0};
int j=0;

while(test--){
int n;
cin>n;
ll ans = res[n];
ans = (ans+N)%N;
v[j++]=ans;
}
for(int i = 0;i<j;i++)
cout << v[i] << '\n';

}

import java.util.*;
import java.io.*;

public class Main {

static int N = 1000000007;
static int maxn = 2000001;
static long phi[] = new long[maxn];
static long res[] = new long[maxn];

static void pre()
{
int i,j;
for(i=1;i<maxn;i++)
phi[i] = i;
for(i=2;i<maxn;i++)
{
if(phi[i] == i)
{
for(j=i;j<maxn;j=j+i)
{
phi[j] = (phi[j]/i)*(i-1);
}
}
}
for(i=2;i<maxn;i++)
for(j=i;j<maxn;j=j+i)
res[j] = (res[j] + ((((long)i*i)%N)*((phi[i]*500000004)%N))%N)%N;

for(i=2;i<maxn;i++)
res[i] = (((res[i] + res[i-1])+N) %N)%N;
}

public static void main(String args[]) throws IOException {

pre();

while(test--!=0){
long ans = res[n];
ans = (ans+N)%N;
System.out.println(ans);
}
br.close();
}
}
`

[forminator_quiz id="847"]

This article tried to discuss Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Mathematics you can check out MYCODE | Competitive Programming.