HackerRank GCD Matrix Problem Solution

In this post, we will solve HackerRank GCD Matrix Problem Solution.

Alex has two arrays defined as A = [ao, a1,…, an-1] and B = [bo, b1, bm-1]. He
created an n x m matrix, M, where M = gcd(a, b) for each i, j in M. Recall that
gcd (a, b) is the greatest common divisor of a and b.
For example, if A = [2, 3] and B = [5, 6], he builds M = [[1, 2], [1, 3]] like so:
Alex’s friend Kiara loves matrices, so he gives her q questions about matrix M where each question is in the form of some submatrix of M with its upper-left corner at Me, and its bottom-right corner at Mr₂,c₂- For each question, find and print the number of distinct integers in the given submatrix on a new line.
Input Format
The first line contains three space-separated integers describing the respective values of n (the size of array A), m (the size of array B), and q (Alex’s number of questions). The second line contains n space-separated integers describing a0, a1,…,an-1. The third line contains m space-separated integers describing bo, b1,…, bm-1. Each line i of the q subsequent lines contains four space-separated integers describing the respective values of r₁, c₁, r₂, and c₂ for the ith question (ie., defining a submatrix with upper-left corner (r1, C1) and bottom-right corner (r2, C2)).

Output Format

For each of Alex’s questions, print the number of distinct integers in the given submatrix on a new line.

Sample Input 0

Sample Output 0

2
3
3

GCD Matrix C Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[100000],b[100000];
long long dp1[100000],dp2[100000],dp[100000];

int main(){
  int n,m,q,r1,r2,c1,c2,ans,i,j;
  scanf("%d%d%d",&n,&m,&q);
  for(i=0;i<n;i++)
    scanf("%d",a+i);
  for(i=0;i<m;i++)
    scanf("%d",b+i);
  while(q--){
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    memset(dp,0,sizeof(dp));
    scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
    for(i=r1;i<=r2;i++)
      for(j=1;j*j<=a[i];j++)
        if(a[i]%j==0){
          dp1[j-1]++;
          if(j*j!=a[i])
            dp1[a[i]/j-1]++;
        }
    for(i=c1;i<=c2;i++)
      for(j=1;j*j<=b[i];j++)
        if(b[i]%j==0){
          dp2[j-1]++;
          if(j*j!=b[i])
            dp2[b[i]/j-1]++;
        }
    for(i=99999,ans=0;i>=0;i--){
      dp[i]+=dp1[i]*dp2[i];
      if(dp[i]>0){
        ans++;
        dp[0]-=dp[i];
        for(j=2;j*j<=i+1;j++)
          if((i+1)%j==0){
            dp[j-1]-=dp[i];
            if(j*j!=i+1)
              dp[(i+1)/j-1]-=dp[i];
          }
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

GCD Matrix C++ Solution

#include <bits/stdc++.h>
// #include "testlib.h"  
using namespace std ;

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)

#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)

#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)

#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

const int mod = 1e9 + 7;

int ADD(int a, int b, int m = mod) {
    int s = a;
    s += b;
    if( s >= m )
      s -= m;
    return s;
}

int MUL(int a, int b, int m = mod) {
    return (1LL * a * b % m);
}

int power(int a, int b, int m = mod) {
    int res = 1;
    while( b ) {
        if( b & 1 ) {
            res = 1LL * res * a % m;
        }
        a = 1LL * a * a % m;
        b /= 2;
    }
    return res;
}

ll nC2(ll x) {
    return ( x * ( x - 1 ) / 2 );
}

const int maxn = 1e5 + 5;

int A[maxn], B[maxn];
ll d[maxn];
int a[maxn], b[maxn];
int n, m, q;
void reset() {
    int i; fr(i, 1, maxn-1) {
        a[i] = b[i] = d[i] = 0;
    } 
}

void solve() {
    reset();
    int i, w, x, y, z;
    cin >> w >> x >> y >> z; w++; x++; y++; z++;
    assert(1 <= w && w <= n);
    assert(1 <= y && y <= n);
    assert(w <= y && x <= z);
    assert(1 <= x && x <= m);
    assert(1 <= z && z <= m);
    fr(i, w, y) a[A[i]] ++;
    fr(i, x, z) b[B[i]] ++;
    fr(i, 1, maxn-5) {
        int j = i, v1 = 0, v2 = 0;
        while( j <= maxn-5 ) {
            v1 += a[j];
            v2 += b[j];    
            j += i;
        } 
        a[i] = v1; b[i] = v2;
    }

    int cnt = 0;
    fb(i, maxn-5, 1) {
        int j = i; ll ans = 0;
        ans = 1LL * a[i] * b[i];
        while(j <= maxn-5) {
            ans -= d[j];
            j += i;
        }
        d[i] = ans;
        if( d[i] ) cnt ++;
    }
    cout << cnt << "\n";
}
int main() {
    cin >> n >> m >> q;
    assert(1 <= n && n <= 100000);
    assert(1 <= m && m <= 100000);
    assert(q <= 10 && q >= 1);
    int i; 
    fr(i, 1, n) {
        cin >> A[i];
        assert(A[i] <= 100000 && A[i] >= 1);
    }
    fr(i, 1, m) {
        cin >> B[i];
        assert(B[i] <= 100000 && B[i] >= 1);
    }
    while( q-- ) solve();
    return 0;
}

GCD Matrix C Sharp Solution

using System;
using System.Linq;

namespace HackerRank
{
    class GcdMatrix
    {
        static void Main(string[] args)
        {
            var tokens = Console.ReadLine().Split(' ').ToArray();

            var N = Convert.ToInt32(tokens[0]);
            var M = Convert.ToInt32(tokens[1]);
            var Q = Convert.ToInt32(tokens[2]);

            var A = Console.ReadLine().Split(' ').Select(x => Convert.ToInt32(x)).ToArray();
            var B = Console.ReadLine().Split(' ').Select(x => Convert.ToInt32(x)).ToArray();

            for (var q = 0; q < Q; q++)
            {
                tokens = Console.ReadLine().Split(' ').ToArray();

                var r1 = Convert.ToInt32(tokens[0]);
                var c1 = Convert.ToInt32(tokens[1]);

                var r2 = Convert.ToInt32(tokens[2]);
                var c2 = Convert.ToInt32(tokens[3]);

                var MAX = Math.Max(A.Skip(r1).Take(r2 - r1 + 1).Max(), B.Skip(c1).Take(c2 - c1 + 1).Max());

                var freqA = new int[MAX + 1];

                for (var i = r1; i <= r2; i++)
                {
                    freqA[A[i]]++;
                }

                var freqB = new int[MAX + 1];

                for (var j = c1; j <= c2; j++)
                {
                    freqB[B[j]]++;
                }

                var numberOfItemsGCDDividesInA = new long[MAX + 1]; // numberOfItemsGCDDividesInA[x] -> number of items divided by x in A.
                var numberOfItemsGCDDividesInB = new long[MAX + 1]; // numberOfItemsGCDDividesInB[x] -> number of items divided by x in B.

                // For every possible GCD
                for (var k = 1; k <= MAX; k++)
                {
                    var gcd = k;

                    do
                    {
                        numberOfItemsGCDDividesInA[k] += freqA[gcd];
                        numberOfItemsGCDDividesInB[k] += freqB[gcd];
                        gcd += k;
                    }
                    while (gcd <= MAX);
                }

                var numberOfPairsPerGCD = new long[MAX + 1];

                // For every possible GCD, in descending order
                for (var k = MAX; k >= 1; k--)
                {
                    var gcd = k;

                    numberOfPairsPerGCD[k] = numberOfItemsGCDDividesInA[k] * numberOfItemsGCDDividesInB[k];

                    gcd += gcd;

                    while (gcd <= MAX)
                    {   // Don't count the pairs already handled by larger GCDs.
                        numberOfPairsPerGCD[k] -= numberOfPairsPerGCD[gcd];
                        gcd += k;
                    }
                }

                var numberOfDistinctDivisors = numberOfPairsPerGCD.Count(x => x > 0);

                Console.WriteLine(numberOfDistinctDivisors);
            }
        }
    }
}

GCD Matrix Java Solution

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class C2 {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni(), m = ni(), Q = ni();
        int[] a = na(n);
        int[] b = na(m);
        for(int z = 0;z < Q;z++){
            int dist = 0;
            int r1 = ni(), c1 = ni(), r2 = ni(), c2 = ni();
            int[] fr = make(a, r1, r2);
            int[] fc = make(b, c1, c2);
            long[] f = new long[100005];
            for(int i = 0;i < 100005;i++)f[i] = (long)fr[i] * fc[i];
            for(int i = 100004;i >= 1;i--){
                for(int j = 2*i;j < 100005;j+=i){
                    f[i] -= f[j];
                }
            }
            for(int i = 0;i < 100005;i++){
                assert f[i] >= 0;
                if(f[i] > 0)dist++;
            }
            out.println(dist);
        }
    }
    
    int[] make(int[] a, int l, int r)
    {
        int[] f = new int[100005];
        for(int i = l;i <= r;i++){
            for(int d = 1;d*d <= a[i];d++){
                if(a[i] % d == 0){
                    f[d]++;
                    if(d*d < a[i])f[a[i]/d]++;
                }
            }
        }
        return f;
    }
    
    public static long gcd3(long a, long b) {
        if(a == 0)return b;
        if(b == 0)return a;
        
        int ashift = Long.numberOfTrailingZeros(a);
        int bshift = Long.numberOfTrailingZeros(b);
        a >>>= ashift;
        b >>>= bshift;
        while(b != a){
            if(a > b){
                long t = a; a = b; b = t;
            }
            b -= a;
            b >>>= Long.numberOfTrailingZeros(b);
        }
        
        return a<<Math.min(ashift, bshift);
    }

    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { 
     new C2().run(); }
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } 
            catch (IOException e) { 
              throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { 
    return !(c >= 33 && c <= 126); }
    private int skip() { 
    int b; while((b = readByte()) != -1 && isSpaceChar(b)); 
    return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){
        // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) {
    System.out.println(Arrays.deepToString(o)); }
}

GCD Matrix Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

def f(k):
    if gf[k]>=0:
        return gf[k]
    res=ga[k]*gb[k]
    if res==0:
        gf[k]=0
        return 0
    for i in range(k+k,m+1,k):
        res-=f(i)
    gf[k]=res
    return res

if __name__ == '__main__':
    nmq = input().split()

    n = int(nmq[0])

    m = int(nmq[1])

    q = int(nmq[2])

    a = list(map(int, input().rstrip().split()))

    b = list(map(int, input().rstrip().split()))

    for q_itr in range(q):
        r1C1R2C2 = input().split()

        r1 = int(r1C1R2C2[0])

        c1 = int(r1C1R2C2[1])

        r2 = int(r1C1R2C2[2])

        c2 = int(r1C1R2C2[3])

        # Write Your Code Here
        sa=set(a[r1:r2+1])
        sb=set(b[c1:c2+1])
        na=len(a)
        nb=len(b)
        mxa=max(sa)
        mxb=max(sb)
        m=min(mxa,mxb)
        mm=max(mxa,mxb)

        ga=[0]*(m+1)
        gb=[0]*(m+1)
        ga[1]=na
        gb[1]=nb

        for i in range(2,m+1):
            for j in range(i,mm+1,i):
                if j in sa:
                    ga[i]+=1
                if j in sb:
                    gb[i]+=1
        gf=[-1]*(m+1)

        f(1)
        r=sum([(x>0) for x in gf])
        print(r)

c C# C++ HackerRank Solutions java python C cpp CSharp Hackerrank Solutions java python