LCC/Moose '19 Contest 4 S4 - Limited Factors

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

Tara recently discovered that each integer can be factored into prime numbers. She first found the process of factoring numbers really exciting, but quickly grew tired of its repetitiveness.

In order to make factoring more challenging, she has decided to limit the factors that she’s allowed to use to N of her favourite numbers. She would now like to figure out which numbers are factorable using the N numbers. Can you help her out?

Input Specification

The input begins with an integer N (1 \le N \le 10^5), the number of factors that Tara is allowed to use.

The second line contains N integers A_i (1 \le A_i \le 10^6), the allowed factors.

The third line contains a single integer M (1 \le M \le 10), the number of integers to factor.

The fourth line contains M integers B_i (2 \le B_i \le 10^{12}), the numbers to factor.

For at least 20% of points, each A_i will be prime.

For at least 50% of points, N \le 40.

Output Specification

For each of the M numbers to factor, output a 1 if it is possible to factor the number using the allowed factors, or 0 otherwise. Each number should be considered independently of the rest.

Sample Input 1

4
2 5 6 8
4
10 4 48 15

Sample Output 1

1110

Comments

There are no comments at the moment.