Couple Cover
Contest: Educational Codeforces Round 14
Difficulty rating: 2200
Tags: brute force, dp, number theory

Couple Cover, a wildly popular luck-based game, is about to begin! Two players must work together to construct a rectangle. A bag with n balls, each with an integer written on it, is placed on the table. The first player reaches in and grabs a ball randomly (all balls have equal probability of being chosen) — the number written on this ball is the rectangle's width in meters. This ball is not returned to the bag, and the second player reaches into the bag and grabs another ball — the number written on this ball is the rectangle's height in meters. If the area of the rectangle is greater than or equal some threshold p square meters, the players win. Otherwise, they lose.

The organizers of the game are trying to select an appropriate value for p so that the probability of a couple winning is not too high and not too low, but they are slow at counting, so they have hired you to answer some questions for them. You are given a list of the numbers written on the balls, the organizers would like to know how many winning pairs of balls exist for different values of p. Note that two pairs are different if either the first or the second ball is different between the two in pair, and two different balls with the same number are considered different.

Input format:
The input begins with a single positive integer n in its own line (1 ≤ n ≤ 106).

The second line contains n positive integers — the i-th number in this line is equal to ai (1 ≤ ai ≤ 3·106), the number written on the i-th ball.

The next line contains an integer m (1 ≤ m ≤ 106), the number of questions you are being asked.

Then, the following line contains m positive integers — the j-th number in this line is equal to the value of p (1 ≤ p ≤ 3·106) in the j-th question you are being asked.

Output format:
For each question, print the number of winning pairs of balls that exist for the given value of p in the separate line.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
5
4 2 6 1 3
4
1 3 5 8

Example output:
20
18
14
10

Example input:
2
5 6
2
30 31

Example output:
2
0

Editorial:
This problem can be solved by pre-computing the answers for all possible queries, and then looking up these answers to respond to the queries in O(1) time. Firstly, construct a frequency array f, such that f[i] is the number of balls with the number i written on them. This will be used to form a new array p, such that p[i] is the number of ways to choose a pair with product exactly equal to i. For each possible number x on the first ball, iterate over all multiples of x. The number of ways to form a product exactly equal to k*x, in which x is written on the first ball chosen, is equal to f[x] * f[k], so increment p[k * x] by this quantity.
Note that the total runtime of these operations, if n is the maximum possible product we are considering, is equal to n * (1/1 + 1/2 + 1/3 + ... + 1/n). This can be rewritten as n * (1/1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + ...), grouping the terms of the summation into groups with sizes equal to increasing powers of two (1 in the first group, 2 in the second group, ..., 2^(k-1) in the kth group). Also, since the terms within each group are decreasing, the sum of a group with size a and the first term b is less than or equal to a/b. The first term of the kth group is 1/(2^(k-1)), and the size of the kth group is 2^(k-1), so the sum of the terms in the kth group is no more than 1. There are O(log(n)) groups, since the size of the groups is doubling each time, so the total number of operations needed to fill p is O(n * log(n)).
Once we have the array p, create a suffix sum array s as follows: s[n-1] = p[n-1]. s[k] = s[k+1] + p[k] for k from n-2 to 0. Then, s[i] is the number of ways to form a product of at least i square meters, which is the answer to a query p = i.