Cerinta completa

Alex has two arrays defined as and . He created an matrix, , where for each in . Recall that is the greatest common divisor of and .

For example, if and , he builds like so:

Alex’s friend Kiara loves matrices, so he gives her questions about matrix where each question is in the form of some submatrix of with its upper-left corner at and its bottom-right corner at . 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 (the size of array ), (the size of array ), and (Alex’s number of questions).
The second line contains space-separated integers describing .
The third line contains space-separated integers describing .
Each line of the subsequent lines contains four space-separated integers describing the respective values of , , , and for the question (i.e., defining a submatrix with upper-left corner and bottom-right corner ).

Constraints

Scoring

  • for of score.
  • for of score.

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 2

Sample Output 0

2
3
3

Explanation 0

Given and , we build the following :

The diagram below depicts the submatrices for each of the questions in green:

image

  1. For the submatrix between and , the set of integers is . The number of distinct integers is .
  2. For the submatrix between and , the set of integers is . The number of distinct integers is .
  3. For the submatrix between and , the set of integers is . The number of distinct integers is .

Limbajul de programare folosit: cpp14

Cod:

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

Scor obtinut: 1.0

Submission ID: 464647685

Link challenge: https://www.hackerrank.com/challenges/gcd-matrix/problem

GCD Matrix