5730: 升级阵列
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：3
通过：2
题目描述
D. 升级阵列
每次测试的时间限制
1 秒
每个测试的内存限制
256 兆字节
输入
标准输入
输出
标准输出
你有一个正整数 a[1]，a[2],...,a[n] 数组和一组坏素数 b 1，b 2,...,bm。集合 b 中没有出现的素数被认为是好的。数组 a 的美妙之处在于和
，其中函数 f（s） 确定如下：
，其中函数 f（s） 确定如下：- f（1）=0;
-
假设 p 是 s 的最小素数除数。如果 p 是一个好的素数，那么
，否则
。
- 选择一些数字 r （1≤r≤n） 并计算值 g = GCD（a[1]，a[2],...,a[r]）。
-
应用赋值：
、、...、
。
输入
第一行包含两个整数 n 和 m （1≤n，m≤5000），显示数组中有多少个数字以及有多少个坏素数。第二行包含 n 个空格分隔的整数 a[1]，a[2],...,a[n] （1≤a[i]≤109） − 数组 a。第三行包含 m 空格分隔的整数 b 1，b 2,...,b m （2≤b 1<b2<...<bm≤109） − 坏素数的集合。
输出
打印单个整数 - 问题的答案。
例子
输入
5 2 4 20 34 10 10 2 5
输出
-2
输入
4 5 2 4 8 16 3 5 7 11 17
输出
10
注意
请注意，问题的答案可能是否定的。GCD（x 1， x 2， ...， x k） 是除以每个 xi 的最大正整数。
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You have an array of positive integers a[1],a[2],...,a[n] and a set of bad prime numbers b1,b2,...,bm. The prime numbers that do not occur in the set b are considered good. The beauty of array a is the sum 
, where function f(s) is determined as follows:
, where function f(s) is determined as follows: - f(1)=0;
-
Let's assume that p is the minimum prime divisor of s. If p is a good prime, then
, otherwise 
.
- Choose some number r (1≤r≤n) and calculate the value g = GCD(a[1],a[2],...,a[r]).
-
Apply the assignments:
, 
, ..., 
.
Input
The first line contains two integers n and m (1≤n,m≤5000) showing how many numbers are in the array and how many bad prime numbers there are. The second line contains n space-separated integers a[1],a[2],...,a[n] (1≤a[i]≤109) − array a. The third line contains m space-separated integers b1,b2,...,bm (2≤b1<b2<...<bm≤109) − the set of bad prime numbers.
Output
Print a single integer − the answer to the problem.
Examples
Input
5 2 4 20 34 10 10 2 5
Output
-2
Input
4 5 2 4 8 16 3 5 7 11 17
Output
10
Note
Note that the answer to the problem can be negative. The GCD(x1, x2, ..., xk) is the maximum positive integer that divides each xi.
输入样例 复制
输出样例 复制