Couple Cover (Codeforces 691F)
Tags: 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: 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: For each question, print the number of winning pairs of balls that exist for the given value of p in the separate line.


Sample Inputs:
5
4 2 6 1 3
4
1 3 5 8

2
5 6
2
30 31

Sample Outputs:
20
18
14
10

2
0

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n = int(input())
l = 3 * pow(10, 6) + 5
cnt = [0] * l
for i in list(map(int, input().split())):
    cnt[i] += 1
(c1, c2) = ([0] * l, [0] * l)
m0 = pow(10, 8)
for i in range(1, l):
    ci = cnt[i]
    if i * i < l:
        j = i * i
        c1[j] += ci * (ci - 1) // m0
        c2[j] += ci * (ci - 1) % m0
        if c2[j] > m0:
            c1[j] += 1
            c2[j] %= m0
    else:
        break
    j = i * (i + 1)
    while j < l:
        cj = cnt[j // i]
        c1[j] += 2 * ci * cj // m0
        c2[j] += 2 * ci * cj % m0
        if c2[j] > m0:
            c1[j] += 1
            c2[j] %= m0
        j += i
n0 = n * (n - 1)
for i in range(1, l):
    c1[i] += c1[i - 1]
    c2[i] += c2[i - 1]
    if c2[i] > m0:
        c1[i] += 1
        c2[i] %= m0
m = int(input())
for i in list(map(int, input().split())):
    ans = n0 - (m0 * c1[i - 1] + c2[i - 1])
    print(ans)

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
from itertools import accumulate, combinations, permutations
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')
n = II()
nums = LII()
cnt = [0] * (3 * 10 ** 6 + 1)
for num in nums:
    cnt[num] += 1
pair_count = [0] * (3 * 10 ** 6 + 2)
key = [num for num in range(1, 10 ** 6 + 1) if cnt[num]]
tot = n
for i in range(len(key)):
    pair_count[min(3 * 10 ** 6 + 1, key[i] * key[i])] += cnt[key[i]] * (cnt[key[i]] - 1)
    tot -= cnt[key[i]]
    tmp = tot
    for j in range(i + 1, len(key)):
        v = key[i] * key[j]
        if v <= 3 * 10 ** 6:
            pair_count[v] += cnt[key[i]] * cnt[key[j]] * 2
        else:
            pair_count[3 * 10 ** 6 + 1] += cnt[key[i]] * tmp * 2
        tmp -= cnt[j]
for i in range(1, 3 * 10 ** 6 + 2):
    pair_count[i] += pair_count[i - 1]
m = II()
queries = LII()
for q in queries:
    print(n * (n - 1) - pair_count[q - 1])

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
l = 3 * pow(10, 6) + 5
cnt = [0] * l
for i in list(map(int, input().split())):
    cnt[i] += 1
c1 = cnt[1]
c = [2 * c1 * cnt[j] for j in range(l)]
c[1] = c1 * (c1 - 1)
for i in range(2, l // 2):
    ci = cnt[i]
    if i * i < l:
        c[i * i] += ci * (ci - 1)
    j = i + 1
    while i * j < l:
        c[i * j] += 2 * ci * cnt[j]
        j += 1
n0 = n * (n - 1)
for i in range(1, l):
    c[i] += c[i - 1]
m = int(input())
ans = []
for i in list(map(int, input().split())):
    ans0 = n0 - c[i - 1]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))