Cowslip Collections (Codeforces 645F)
Tags: Math, combinatorics

In an attempt to make peace with the Mischievious Mess Makers, Bessie and Farmer John are planning to plant some flower gardens to complement the lush, grassy fields of Bovinia. As any good horticulturist knows, each garden they plant must have the exact same arrangement of flowers. Initially, Farmer John has n different species of flowers he can plant, with ai flowers of the i-th species.On each of the next q days, Farmer John will receive a batch of flowers of a new species. On day j, he will receive cj flowers of the same species, but of a different species from those Farmer John already has. Farmer John, knowing the right balance between extravagance and minimalism, wants exactly k species of flowers to be used. Furthermore, to reduce waste, each flower of the k species Farmer John chooses must be planted in some garden. And each of the gardens must be identical; that is to say that each of the k chosen species should have an equal number of flowers in each garden. As Farmer John is a proponent of national equality, he would like to create the greatest number of gardens possible.After receiving flowers on each of these q days, Farmer John would like to know the sum, over all possible choices of k species, of the maximum number of gardens he could create. Since this could be a large number, you should output your result modulo 109 + 7.

Input: The first line of the input contains three integers n, k and q (1 ≤ k ≤ n ≤ 100 000, 1 ≤ q ≤ 100 000).The i-th (1 ≤ i ≤ n) of the next n lines of the input contains an integer ai (1 ≤ ai ≤ 1 000 000), the number of flowers of species i Farmer John has initially.The j-th (1 ≤ j ≤ q) of the next q lines of the input contains an integer cj (1 ≤ cj ≤ 1 000 000), the number of flowers of a new species Farmer John receives on day j.

Output: After each of the q days, output the sum of the maximum possible number of gardens, where the sum is taken over all possible choices of k species, modulo 109 + 7.

Note: In the first sample case, after the first day Farmer John has (4, 6, 9, 8) of each type of flower, and k = 3.Choosing (4, 6, 8) lets him make 2 gardens, each with (2, 3, 4) of each flower, respectively. Choosing (4, 6, 9), (4, 9, 8) and (6, 9, 8) each only let him make one garden, since there is no number of gardens that each species can be evenly split into. So the sum over all choices of k = 3 flowers is 2 + 1 + 1 + 1 = 5.After the second day, Farmer John has (4, 6, 9, 8, 6) of each flower. The sum over all choices is 1 + 2 + 2 + 1 + 1 + 2 + 2 + 3 + 1 + 1 = 16.In the second sample case, k = 1. With x flowers Farmer John can make x gardens. So the answers to the queries are 6 + 5 + 4 + 3 + 2 = 20 and 6 + 5 + 4 + 3 + 2 + 1 = 21.

Sample Inputs:
3 3 2
4
6
9
8
6

4 1 2
6
5
4
3
2
1

Sample Outputs:
5
16

20
21

Solution (Python):
from sys import stdin
from sys import stdout
MOD = 1000000007
MAXA = 1000007
MAXN = 200007
p = [0 for i in range(MAXA)]
phi = [i for i in range(MAXA)]
cant = [0 for _ in range(MAXA)]
combin = [0 for _ in range(MAXA)]

def ComputePhi():
    p[1] = p[0] = 1
    for i in range(1, MAXA):
        for j in range(i, MAXA, i):
            if p[i] == 0:
                if i != j:
                    p[j] = 1
                phi[j] = phi[j] // i * (i - 1)
            if dt.get(j) != None:
                div[dt[j]].append(i)

def qp(a, p):
    a = int(a)
    p = int(p)
    if p == 0:
        return 1
    x = qp(a, p // 2)
    x = x * x % MOD
    if p % 2 == 1:
        x = x * a % MOD
    return x

def inv(a):
    return qp(a, MOD - 2)
inputs = list(map(int, stdin.readline().split()))
(n, k, q) = (inputs[0], inputs[1], inputs[2])
fact = [0 for i in range(MAXN)]
ifact = [0 for i in range(MAXN)]

def comb(a, b):
    if a - b < 0:
        return 0
    return fact[a] * ifact[b] % MOD * ifact[a - b] % MOD
fact[0] = 1
for i in range(1, MAXN):
    fact[i] = fact[i - 1] * i % MOD
ifact[MAXN - 1] = inv(fact[MAXN - 1])
for i in range(MAXN - 2, -1, -1):
    ifact[i] = ifact[i + 1] * (i + 1) % MOD
dt = {}
ln = []
c = 0
for j in range(n):
    a = int(stdin.readline())
    if dt.get(a) == None:
        c += 1
        dt[a] = c
    ln.append(a)
lq = []
for _ in range(q):
    a = int(stdin.readline())
    if dt.get(a) == None:
        c += 1
        dt[a] = c
    lq.append(a)
div = [[] for _ in range(c + 1)]
ComputePhi()
for a in ln:
    for i in div[dt[a]]:
        cant[i] += 1
ans = 0
for i in range(1, MAXA):
    combin[i] = comb(cant[i], k)
    ans += phi[i] * combin[i] % MOD
    ans %= MOD
for a in lq:
    for i in div[dt[a]]:
        ans -= combin[i] * phi[i] % MOD
        ans %= MOD
        if ans < 0:
            ans += MOD
        cant[i] += 1
        combin[i] = comb(cant[i], k)
        ans += combin[i] * phi[i] % MOD
        ans %= MOD
    print(ans)

Solution (Python):
from sys import stdin
from sys import stdout
MOD = 1000000007
MAXA = 1000007
MAXN = 200007
p = [0 for i in range(MAXA)]
phi = [i for i in range(MAXA)]
cant = [0 for _ in range(MAXA)]
combin = [0 for _ in range(MAXA)]

def ComputePhi():
    p[1] = p[0] = 1
    for i in range(1, MAXA):
        for j in range(i, MAXA, i):
            if p[i] == 0:
                if i != j:
                    p[j] = 1
                phi[j] = phi[j] // i * (i - 1)
            if dt.get(j) != None:
                div[dt[j]].append(i)

def qp(a, p):
    a = int(a)
    p = int(p)
    if p == 0:
        return 1
    x = qp(a, p // 2)
    x = x * x % MOD
    if p % 2 == 1:
        x = x * a % MOD
    return x

def inv(a):
    return qp(a, MOD - 2)
inputs = list(map(int, stdin.readline().split()))
(n, k, q) = (inputs[0], inputs[1], inputs[2])
fact = [0 for i in range(MAXN)]
ifact = [0 for i in range(MAXN)]

def comb(a, b):
    if a - b < 0:
        return 0
    return fact[a] * ifact[b] % MOD * ifact[a - b] % MOD
fact[0] = 1
for i in range(1, MAXN):
    fact[i] = fact[i - 1] * i % MOD
ifact[MAXN - 1] = inv(fact[MAXN - 1])
for i in range(MAXN - 2, -1, -1):
    ifact[i] = ifact[i + 1] * (i + 1) % MOD
dt = {}
ln = []
c = 0
for j in range(n):
    a = int(stdin.readline())
    if dt.get(a) == None:
        c += 1
        dt[a] = c
    ln.append(a)
lq = []
for _ in range(q):
    a = int(stdin.readline())
    if dt.get(a) == None:
        c += 1
        dt[a] = c
    lq.append(a)
div = [[] for _ in range(c + 1)]
ComputePhi()
for a in ln:
    for i in div[dt[a]]:
        cant[i] += 1
ans = 0
for i in range(1, MAXA):
    combin[i] = comb(cant[i], k)
    ans += phi[i] * combin[i] % MOD
    ans %= MOD
for a in lq:
    for i in div[dt[a]]:
        ans -= combin[i] * phi[i] % MOD
        ans %= MOD
        if ans < 0:
            ans += MOD
        cant[i] += 1
        combin[i] = comb(cant[i], k)
        ans += combin[i] * phi[i] % MOD
        ans %= MOD
    print(ans)

Solution (Python):
from sys import stdin
from sys import stdout
MOD = 1000000007
MAXA = 1000007
MAXN = 200007
p = [0 for i in range(MAXA)]
phi = [i for i in range(MAXA)]
cant = [0 for _ in range(MAXA)]
combin = [0 for _ in range(MAXA)]

def ComputePhi():
    p[1] = p[0] = 1
    for i in range(1, MAXA):
        for j in range(i, MAXA, i):
            if p[i] == 0:
                if i != j:
                    p[j] = 1
                phi[j] = phi[j] // i * (i - 1)
            if dt.get(j) != None:
                div[dt[j]].append(i)

def qp(a, p):
    a = int(a)
    p = int(p)
    if p == 0:
        return 1
    x = qp(a, p // 2)
    x = x * x % MOD
    if p % 2 == 1:
        x = x * a % MOD
    return x

def inv(a):
    return qp(a, MOD - 2)
inputs = list(map(int, stdin.readline().split()))
(n, k, q) = (inputs[0], inputs[1], inputs[2])
fact = [0 for i in range(MAXN)]
ifact = [0 for i in range(MAXN)]

def comb(a, b):
    if a - b < 0:
        return 0
    return fact[a] * ifact[b] % MOD * ifact[a - b] % MOD
fact[0] = 1
for i in range(1, MAXN):
    fact[i] = fact[i - 1] * i % MOD
ifact[MAXN - 1] = inv(fact[MAXN - 1])
for i in range(MAXN - 2, -1, -1):
    ifact[i] = ifact[i + 1] * (i + 1) % MOD
dt = {}
ln = []
c = 0
for j in range(n):
    a = int(stdin.readline())
    if dt.get(a) == None:
        c += 1
        dt[a] = c
    ln.append(a)
lq = []
for _ in range(q):
    a = int(stdin.readline())
    if dt.get(a) == None:
        c += 1
        dt[a] = c
    lq.append(a)
div = [[] for _ in range(c + 1)]
ComputePhi()
for a in ln:
    for i in div[dt[a]]:
        cant[i] += 1
ans = 0
for i in range(1, MAXA):
    combin[i] = comb(cant[i], k)
    ans += phi[i] * combin[i] % MOD
    ans %= MOD
for a in lq:
    for i in div[dt[a]]:
        ans -= combin[i] * phi[i] % MOD
        ans %= MOD
        if ans < 0:
            ans += MOD
        cant[i] += 1
        combin[i] = comb(cant[i], k)
        ans += combin[i] * phi[i] % MOD
        ans %= MOD
    print(ans)