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])

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)

{"mode":"full","isActive":false}

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 {
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]);

int result = gdcMatrix(r1, c1, r2, c2);

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

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

{"mode":"full","isActive":false}

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;
}

{"mode":"full","isActive":false}

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("%d\n",ans);
}
return 0;
}

{"mode":"full","isActive":false}