Problem:


Problem F: Remainder Zero

Problem

  整数の集合A,Bについて,次の条件を満たす整数 xがいくつ存在するか答えよ。

Ai mod x = 0 かつ x mod Bj = 0 がすべての i (1 ≤ i ≤ N), j (1 ≤ j ≤ M) について成り立つ。

(a mod b はaをbで割ったときの余りを意味する)

Input

N M
A1 A2 ... AN
B1 B2 ... BM

Constraints

入力は以下の条件を満たす。

1 ≤ N, M ≤ 5

1 ≤ Ai, Bj ≤ 1014 (1 ≤ i ≤ N, 1 ≤ j ≤ M)

Output

条件を満たす整数 x がいくつ存在するか一行で出力せよ。

Sample Input 1

1 2
18
6 9

Sample Output 1

1

Sample Input 2

1 2
256
2 4

Sample Output 2

7



Sample input:
1 2
18
6 9


Sample output:
1

Submission status: Accepted

Solution code:
from math import gcd
def main():
  n, m = map(int, input().split())
  alst = list(map(int, input().split()))
  blst = list(map(int, input().split()))
  g1 = alst[0]
  for i in range(1, n):
    g1 = gcd(g1, alst[i])
  
  l2 = blst[0]
  for i in range(1, m):
    g2 = gcd(l2, blst[i])
    l2 = l2 * blst[i] // g2
  
  if g1 % l2 != 0:print(0)
  else:
    x = g1 // l2
    ans = 1
    for solver in range(2, 10000000):
      if solver > x:break
      cnt = 1
      while x % solver == 0:
        cnt += 1
        x //= solver
      ans *= cnt
    print(ans)
  
main()