HackerRank GCD Matrix problem solution

In this HackerRank GCD Matrix problem solution, we have given Q questions about matrix M where each question is in the form of some submatrix of M with its upper-left corner at Mr1c1 and its bottom-right corner at Mr2c2. For each question, find and print the number of distinct integers in the given submatrix on a new line.

Problem solution in Python.

#!/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)

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

  static final int MAXN = 100000;
  static final int MAXV = MAXN + 5;

  static final int[] a = new int[MAXV];
  static final int[] b = new int[MAXV];
  static final long[] d = new long[MAXV];
  static final int[] va = new int[MAXV];
  static final int[] vb = new int[MAXV];

  static int gdcMatrix(int w, int x, int y, int z) {
      for (int i = 1; i < MAXV; i++) {
        va[i] = 0;
        vb[i] = 0;
        d[i] = 0;
      } 

      for (int i = w; i <= y; i++) {
          va[a[i]]++;
      }
      for (int i = x; i <= z; i++) {
          vb[b[i]]++;
      }
      for (int i = 1; i <= MAXN; i++) {
          int j = i;
          int v1 = 0;
          int v2 = 0;
          while (j <= MAXN) {
              v1 += va[j];
              v2 += vb[j];
              j += i;
          }
          va[i] = v1;
          vb[i] = v2;
      }

      int cnt = 0;
      for(int i = MAXN; i >= 1; i--) {
          int j = i;
          long ans = 0;
          ans = ((long) va[i]) * vb[i];
          while(j <= MAXN) {
              ans -= d[j];
              j += i;
          }
          d[i] = ans;
          if (d[i] > 0) cnt++;
      }
      return cnt;
  }


    public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
    String[] nmq = br.readLine().replaceAll("\s+$", "").split(" ");

    int n = Integer.parseInt(nmq[0]);

    int m = Integer.parseInt(nmq[1]);

    int q = Integer.parseInt(nmq[2]);

    String[] aItems = br.readLine().replaceAll("\s+$", "").split(" ");

    for (int i = 0; i < n; i++) {
      int aItem = Integer.parseInt(aItems[i]);
      a[i] = aItem;
    }

        String[] bItems = br.readLine().replaceAll("\s+$", "").split(" ");

        for (int i = 0; i < m; i++) {
            int bItem = Integer.parseInt(bItems[i]);
            b[i] = bItem;
        }

        for (int qItr = 0; qItr < q; qItr++) {
            String[] r1C1R2C2 = br.readLine().replaceAll("\s+$", "").split(" ");

            int r1 = Integer.parseInt(r1C1R2C2[0]);

            int c1 = Integer.parseInt(r1C1R2C2[1]);

            int r2 = Integer.parseInt(r1C1R2C2[2]);

            int c2 = Integer.parseInt(r1C1R2C2[3]);

            // Write Your Code Here
            int result = gdcMatrix(r1, c1, r2, c2);

            bw.write(String.valueOf(result));
            bw.newLine();
        }

        br.close();
        bw.close();
    }
}

Problem solution in C++.

#include <iostream>
#include <fstream>
#include <cstring>
#define NMX 100010
#define fin cin
#define fout cout

using namespace std;

int n,m,q,a[NMX],b[NMX],dv[NMX],x1,y1,x2,y2,f1[NMX],f2[NMX],f[NMX];

int desc (int x)
{
    int d=2,pr=0;

    while(x>1)
    {
        if(!(x%d))
        {
            while(!(x%d))
                x/=d,pr++;
        }

        if(d==2)
            d=3;
        else
            if(d*d>=x && x>1)
            d=x;
        else d+=2;
    }

    return pr;
}

int fx[NMX];

int prep (int x, int y, int a[], int f[])
{
    memset(fx,0,sizeof(fx));

    for(int i=x;i<=y;i++)
    {
        fx[a[i]]++;
    }

    f[1]=y-x+1;

    for(int i=2;i<NMX;i++)
    {
        for(int j=1;j*i<NMX;j++)
            f[i]+=fx[i*j];
    }

    return 0;
}

int sm[NMX];

int cmmdc (int a, int b)
{
    int r;

    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }

    return a;
}

int solve ()
{
    int sum=0;

    for(int i=NMX-1;i;i--)
    {
        sm[i]=f1[i]*f2[i];

        long long sum2=0;

        for(int j=2;j*i<NMX;j++)
        {
            sum2+=sm[i*j];
        }

        sm[i]-=sum2;

        if(sm[i])
            sum++;
    }

    if(!sum)
        sum++;

    return sum;
}

int main()
{
    
    fin>>n>>m>>q;

    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
    }

    for(int i=1;i<=m;i++)
    {
        fin>>b[i];
    }

    for(int i=1;i<=q;i++)
    {
        fin>>x1>>y1>>x2>>y2;

        if(x1>x2)
            swap(x1,x2);

        if(y1>y2)
            swap(y1,y2);

        x1++;x2++;y1++;y2++;

        memset(f1,0,sizeof(f1));
        prep(x1,x2,a,f1);

        memset(f2,0,sizeof(f2));
        prep(y1,y2,b,f2);

        fout<<solve()<<"n";
    }


    return 0;
}

Problem solution in C.

#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("%dn",ans);
  }
  return 0;
}