[HackerRank] Between Two Sets c++

• Problem

There will be two arrays of integers. Determine all integers that satisfy the following two conditions:

1. The elements of the first array are all factors of the integer being considered
2. The integer being considered is a factor of all elements of the second array

These numbers are referred to as being between the two arrays. Determine how many such numbers exist.

• Example

a = [2, 6]

b = [24, 36]

There are two numbers between the arrays:  6 and 12.

6%2 = 0, 6%6 = 0. 24%6 = 0. 36%6 = 0 for the first value.

12%2=0, 12%6=0 and 24%12=0, 36%12=0 for the second value. Return 2.

• Constraints

1<= n,m <= 10

1 <= a[i] <= 100

1 <= b[j] <= 100

• Sample Input

2 3
2 4
16 32 96

• Sample Output

3

• Explanation

2 and 4 divide evenly into 4, 8, 12 and 16.
4, 8 and 16 divide evenly into 16, 32, 96.

4, 8 and 16 are the only three numbers for which each element of a is a factor and each is a factor of all elements of b.

• Solutions

문제 설명이 이해가 안가도 sample example을 보면 이해가 갔는데

이 문제는 sample example을 봐도 문제 해석이 어려웠다.

a의 최소공배수이고, b의 최대공약수의 배수를 count하는 문제이다.

 

첫번째 줄 input인 n은 a의 개수, m은 b의 개수이다.

두번째 줄은 a 원소가 주어지고

세번째 줄은 b 원소가 주어진다.

 

int gcd(int a, int b){  //최대공약수 구하기
    if(b > a){
        int temp = b;
        b = a;
        a = temp;
    }
    while(b){
        int c= a % b;
        a = b;
        b = c;
    }
    return a;
}

int lcm(int a, int b){  //최소공배수 구하기
    return a * b / gcd(a, b);
}

int getTotalX(vector<int> a, vector<int> b) {
    int cnt = 0;
    int lcmA = a.at(0), gcdB = b.at(0);
    
    int gcdA = a.at(0);
    for(int i = 1; i < a.size(); i++){ 
        lcmA = lcm(a[i], lcmA);	       //a 원소들의 최소공배수 구하기
        if(lcmA > 100)  return 0;      //runtime error 방지
    }
    for(int i = 1; i < b.size(); i++){
        gcdB = gcd(b[i], gcdB);         //b 원소들의 최대공약수 구하기
    }
    if( (gcdB == 0) || (lcmA > 100) || (lcmA > gcdB) )  return 0;
    
    
    
    for(int i = lcmA; i <= gcdB; i++){   //최소공배수와 최대공약수 사이의 정수 중에서
        if((gcdB%i == 0 )&& (i % lcmA == 0)) cnt++;      
        //최대공약수의 약수이고, 최소공배수의 배수인지 검사
    }
    return cnt;
}

hackerrank between tow sets c++