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