Between Two Sets, Algorithm problem

# Between Two Sets, Algorithm problem

Consider two sets of positive integers, A= {a0,a1…an-1} andA= {b0,b1…bn-1} . 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


Explanation

There are three values between and :

• :
• All the elements in evenly divide .
• evenly divides all the elements in .
• :
• All the elements in evenly divide .
• evenly divides all the elements in .
• :
• All the elements in evenly divide .
• evenly divides all the elements in .

Thus, we print as our answer.

Solution in PHP

If any problem, feel free to comment or contact.


<?php

$handle = fopen ("php://stdin","r"); fscanf($handle,"%d %d",$n,$m);
$a_temp = fgets($handle);
$a = explode(" ",$a_temp);
array_walk($a,'intval');$b_temp = fgets($handle);$b = explode(" ",$b_temp); array_walk($b,'intval');

$lower_bound =$a[$n-1];$upper_bound = $b[0];$count_x = 0;

for($i = 1;$i <= $upper_bound;$i++){
$sum_mod = 0; for($j = 0; $j <$n; $j++){ if ($i%$a[$j]!=0) {
$sum_mod=1; } } for($k = 0; $k <$m; $k++){ if ($b[$k] %$i) {
$sum_mod =1; } } if($sum_mod == 0){
$count_x++; } } echo$count_x;

?>