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 can be referred from online programming courses and it 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:
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();
    }
}
Previous post Beautiful Bracket String (Paid Article and Add Time Complexity)
Next post Beach House

Leave a Reply

Your email address will not be published. Required fields are marked *