Between Two Sets

Consider two sets of positive integers,  and . We say that a positive integer, , is between sets  and  if the following conditions are satisfied:

  1. All elements in  are factors of .
  2.  is a factor of all elements in .

In other words, some  is between  and  if that value of  satisfies  for every  in  and also satisfies  for every  in . For example, if  and , then our possible  values are and .

Given  and , find and print the number of integers (i.e., possible ‘s) that are between the two sets.

Input Format

The first line contains two space-separated integers describing the respective values of  (the number of elements in set ) and  (the number of elements in set ).
The second line contains  distinct space-separated integers describing .
The third line contains  distinct space-separated integers describing .

Constraints

Output Format

Print the number of integers that are considered to be between  and .

Sample Input

2 3
2 4
16 32 96

Sample Output

3

Solution

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function getTotalX(a, b) {
    var maxA = 0, minB = 101, count=0, n=a.length, m=b.length;

    for(var a_i=0; a_i  maxA ? tmpa : maxA;
    }

    for(var b_i=0; b_i < m; b_i++){
        var tmpb = b[b_i];
        minB = tmpb < minB ? tmpb : minB;
    }


  for(var i = maxA; i <= minB; i += maxA)
  {
      var factorA = true, factorB = true;
      //Check if all A are a factor of i
      for(var ii = 0; ii < n; ii++){
          if(i%a[ii] !=0){
              factorA = false;
              continue;
           }
      }

      //Check if i is a factor of all B
      for(var jj = 0; jj < m; jj++){
           if(b[jj]%i != 0){
              factorB = false;
              continue;
            }
      }
      
      if(factorA && factorB)
        count++;
  }
    
  return count;
    
}

function main() {
    var n_temp = readLine().split(' ');
    var n = parseInt(n_temp[0]);
    var m = parseInt(n_temp[1]);
    a = readLine().split(' ');
    a = a.map(Number);
    b = readLine().split(' ');
    b = b.map(Number);
    var total = getTotalX(a, b);
    process.stdout.write("" + total + "\n");

}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s