One more GCD sum

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) Note: Don’t forget to take modulo to avoid overflow.

Example

• Lets assume N to be 10, the phi table for it would be:

• 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:

• 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.