Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Walt and Gus have a great rivalry. Recently Gus has developed a cryptographic system. Walt is trying to crack it. While trying, he has found out that there is an array C of integers lying under the cryptographic system. Walt needs some information about the array C.
Walt has developed an algorithm to generate random integers. He calls the random integers generated by this algorithm as "Crypto-Number". The algorithm is as follows:
Lets simulate the algorithm:
Step 1: The "Crypto-Number" = 1.
Step 2:Let, Walt chooses 81, 3 as r, p respectively. Result of multiplication = 1×813 = 531441.
Step 3: The new value of "Crypto-Number" = 531441.
If Walt repeats the steps 2 and 3 again:
Step 2: Let, Walt chooses 6, 5 as r, p respectively this time. Result of multiplication = 531441×65 = 4132485216.
Step 3: The new value of "Crypto-Number" = 4132485216.
And so on.
Now Walt wants to know, for a Crypto-Number k, how many integers are in the array C such that k is completely divisible by them.
The first line of the input contains an integer N, the size of the array C. The next line will contain N space-separated integers Ci - the elements of the array C.
The next line contains an integer Q, the number of the queries. In each of the next Q lines, there will be an integer k - the "Crypto-Number".
Constraints:
1 ≤ N ≤ 106
1 ≤ Ci ≤ 1012
1 ≤ Q ≤ 104
4 ≤ k ≤ 1012
Subtask 1, For 10 points: 1 ≤ Q ≤ 10, 4 ≤ k ≤ 106
Subtask 2, For 30 points: 1 ≤ Q ≤ 104, 4 ≤ k ≤ 106
Subtask 3, For 60 points: The original constraints.
For each query, print in this format in a single line (without quotes): “Query x: y”, where x is the number of the query and y is the number of the integers in the array C, which integers can completely divide k.
Input | Output |
---|---|
6 1 8 4 18 13 8 4 16 36 8 169 | Query 1: 4 Query 2: 3 Query 3: 4 Query 4: 2 |
Notes: |
14% Solution Ratio
DraakKrijgerFCEarliest,
Gias_UddinFastest, 0.4s
quachanhLightest, 33 MB
user.934670Shortest, 1099B
Login to submit