GCD Matrix
Problem Statement :
Alex has two arrays defined as A = [a0,a1,...,an-1] and B = [b0,b1,...,bm-1]. He created an n*m matrix, M, where Mij = gcd(ai,bj) 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 M(r1,c1) and its bottom-right corner at M(r2,c2). 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 nspace-separated integers describing a0,a1,...,an-1. The third line contains m space-separated integers describing b0,b1,...,bm-1. Each line i of the q subsequent lines contains four space-separated integers describing the respective values of r1, c1, r2, and c2 for the ith question (i.e., defining a submatrix with upper-left corner (r1,c1) and bottom-right corner (r2,c2)). Constraints 1 <= n,m <= 10^5 1 <= ai,bi <= 10^5 1 <= q <= 10 0 <= r1,r2 < n 0 <= c1,c2 < m
Solution :
Solution in C :
In C++ :
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <assert.h>
#include <time.h>
#include <complex.h>
#include <fstream>
#include <sys/stat.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))
#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<Int, Int> PII;
const int INF = 1000000000;
const int MAX = 100007;
const int MAXD = 20;
const int MOD = 1000000007;
int a[MAX];
int b[MAX];
int ca[MAX];
int cb[MAX];
Int A[MAX];
int main()
{
//freopen("in.txt" , "r" , stdin);
//freopen("out.txt" , "w" , stdout);
int n , m;
cin >> n >> m;
int q;
cin >> q;
FOR(i,0,n) cin >> a[i];
FOR(i,0,m) cin >> b[i];
FOR(i,0,q)
{
int r1,c1,r2,c2;
cin >> r1 >> c1 >> r2 >> c2;
FILL(ca , 0);
FILL(cb , 0);
FOR(i,r1,r2 + 1)
ca[a[i]] ++;
FOR(i,c1,c2 + 1)
cb[b[i]] ++;
FILL(A, 0);
FOR(i,1,MAX)
{
int cntA = 0;
int cntB = 0;
for(int j = i; j < MAX; j += i)
{
cntA += ca[j];
cntB += cb[j];
}
A[i] = 1LL * cntA * cntB;
}
int res = 0;
RFOR(i,MAX,1)
{
for(int j = 2 * i; j < MAX; j += i)
A[i] -= A[j];
if (A[i]) ++ res;
}
cout << res << endl;
}
return 0;
}
In Java :
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)); }
}
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;
}
In Python3 :
#!/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)
View More Similar Problems
Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →Tree: Height of a Binary Tree
The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary
View Solution →Tree : Top View
Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.
View Solution →Tree: Level Order Traversal
Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F
View Solution →