Numbers Between Multiples and Divisors

Time limit2sMemory limit128 MB

Summary

Find how many positive integers are simultaneously a common multiple of array D and a common divisor of array M by combining LCM and GCD with divisor counting.

Level: Medium4 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

You are given two arrays of positive integers, D and M. Count the number of positive integers x that satisfy both conditions below.

Every element of D divides x; in other words, x is a common multiple of all elements in D.
x divides every element of M; in other words, x is a common divisor of all elements in M.

Input

The first line contains the sizes N and K of arrays D and M. The second line contains N elements of D. The third line contains K elements of M.

Both N and K are at most 50, and every element is a positive integer not greater than 10^9.

Output

Print the number of positive integers that satisfy the conditions.

Examples5

Example 1
Input
```
1 1
1
100
```
Expected output
```
9
```
Example 2
Input
```
2 1
6 9
18
```
Expected output
```
1
```
Example 3
Input
```
2 2
6 9
96 180
```
Expected output
```
0
```
Example 4
Input
```
2 1
2 4
256
```
Expected output
```
7
```
Example 5
Input
```
3 1
1000 10000 100000
1000000000
```
Expected output
```
25
```