Last Updated on March 25, 2022 by Ria Pathak

### Concepts Used

Mathematics

### Difficulty Level

Hard

### Problem Statement (Simplified):

Calculate the sum for a given number `n`

:

**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 , from above step we can see it becomes,=>

`(i=k*d`

and`j=l*d)`

=>

`(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(`

which is also equal to 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`(`

`)`

and`d`

lies in range`1`

to`n`

, which can be find in`O(`

`)`

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)

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

### 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(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int test = Integer.parseInt(br.readLine()); while(test--!=0){ int n = Integer.parseInt(br.readLine()); 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.