7436: Cookies
内存限制：128 MB
时间限制：5 S
题面：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
Elsa’s elder brother Eric has got n cookies in his icebox and each cookie has a special number written on it. Let’s denote the number written on the ith cookie by fi. fiis defined as follows:
Here, divmed(x) states the median value of divisors of x. Let x has k divisors, then divmed(x) is ⌈k/2⌉th smallest divisor. For example, divmed(100)=10, divmed(10)=2, divmed(1)=1.
One day, Eric opened the icebox and recognized that some of his cookies are missing. His sister Elsa had eaten some of them.
On the first day, she ate cookies that have multiples of p1 as indexes and then, re-indexed them starting from 1 according to their original order. In the same way, she ate cookies with multiples of pi as indexes on the ith day and re-indexed them. If there were less than pi cookies left, she ate none of them. Elsa continued to do so for m days.
As Elsa is keen on math and Eric didn’t want to blame his sister, Eric asked her to find out the number written on the kth of remaining cookies.
Here, divmed(x) states the median value of divisors of x. Let x has k divisors, then divmed(x) is ⌈k/2⌉th smallest divisor. For example, divmed(100)=10, divmed(10)=2, divmed(1)=1.
One day, Eric opened the icebox and recognized that some of his cookies are missing. His sister Elsa had eaten some of them.
On the first day, she ate cookies that have multiples of p1 as indexes and then, re-indexed them starting from 1 according to their original order. In the same way, she ate cookies with multiples of pi as indexes on the ith day and re-indexed them. If there were less than pi cookies left, she ate none of them. Elsa continued to do so for m days.
As Elsa is keen on math and Eric didn’t want to blame his sister, Eric asked her to find out the number written on the kth of remaining cookies.
输入格式
The first line of the input contains an integer T(1≤T≤60), denoting the number of test cases. The first line of each test case contains 3 positive integers n(1≤n≤1010), m(1≤m≤105) and k(1≤k≤1010). The next line contains m integers p1,p2,⋯,pm (1≤pi≤1010).
输出格式
For each test case, output one line containing the answer. If the kth cookie doesn’t exist, then output -1 in a single line.
输入样例 复制
2
25 5 9
3 5 8 12 10
25 5 2
3 5 8 12 10输出样例 复制
31
2