Practice on Toph
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
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 “CryptoNumber”. The algorithm is as follows:
1. Initially, the “CryptoNumber” is = 1.
2. Walt chooses two integers r, p  both greater than 1 randomly. Then he multiplies the “CryptoNumber” with r^{p}.
3. The result of the multiplication is the new value of “CryptoNumber”.
4. He repeats the steps 2 and 3 for a random amount of time.
It is guaranteed that the generated “CryptoNumber” follows this constraint: 4 ≤ CryptoNumber ≤ 10^{12}.
Lets simulate the algorithm:
Step 1: The “CryptoNumber” = 1.
Step 2:Let, Walt chooses 81, 3 as r, p respectively. Result of multiplication = 1×81^{3} = 531441.
Step 3: The new value of “CryptoNumber” = 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×6^{5} = 4132485216.
Step 3: The new value of “CryptoNumber” = 4132485216.
And so on.
Now Walt wants to know, for a CryptoNumber 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 spaceseparated integers C_{i}  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 “CryptoNumber”.
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ C_{i} ≤ 10^{12}
1 ≤ Q ≤ 10^{4}
4 ≤ k ≤ 10^{12}
Subtask 1, For 10 points: 1 ≤ Q ≤ 10, 4 ≤ k ≤ 10^{6}
Subtask 2, For 30 points: 1 ≤ Q ≤ 10^{4}, 4 ≤ k ≤ 10^{6}
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 

14% Solution Ratio
DraakKrijgerFCEarliest,
alamkhanFastest, 0.5s
quachanhLightest, 33 MB
DraakKrijgerFCShortest, 1956B
Login to submit