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
3 3 3
1 2 3
2 4 6
0 0 1 1
0 0 2 2
1 1 2 2Sample 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)
