Between two sets

problem-

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

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.

solutuon-

#include <bits/stdc++.h>

/*

    *

    * Ratnadeep Sen

    * National Institute Of Technology Silchar -India (NITS)

    *

*/

using namespace std;

#define forn(i,n) for (int i = 0; i < int(n); ++i)

const int maxc = 100;

int gcd(int a, int b) {

    while (a && b) {

        if (a >= b)

            a %= b;

        else

            b %= a;

    }

    return a + b;

}

int lcm(int a, int b) {

    return (a / gcd(a, b)) * b;

}

int main() {

    #ifdef LOCAL

    assert(freopen("test.in", "r", stdin));

    #endif

    int n, m;

    cin >> n >> m;

    int A = 1, B = 0;

    forn (i, n) {

        int x;

        cin >> x;

        A = lcm(A, x);

        if (A > maxc) {

            cout << 0 << '\n';

            return 0;

        }

    }

    forn (i, m) {

        int x;

        cin >> x;

        B = gcd(B, x);

    }

    if (B % A != 0) {

        cout << 0 << '\n';

        return 0;

    }

    B /= A;

    int res = 0;

    for (int i = 1; i * i <= B; ++i) {

        if (B % i == 0) {

            ++res;

            if (i * i != B)

                ++res;

        }

    }

    cout << res << '\n';

}