HackerRank Number Theory – GCD Sequence

Challenge: GCD Sequence

Subdomeniu: Number Theory (number-theory)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464775260

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/gcd-sequence/problem

Cerinta

How many non decreasing sequences are there of length $K$, with the condition that numbers in sequence can take values only from $1,2,3, \cdots N$ and gcd of all numbers in the sequence must be $1$.

**Input Format**  
The first line contains an integer $T$ i.e. the number of test cases.<br>
$T$ lines follow, each line containing two integers $N$ and $K$ separated by a single space.  

**Output Format**  
For each testcase, print in a newline the answer $\mod(10^9+7)$. 

**Constraints**  

$ 1 \le T \le 5$  
$ 1 \le N \le  10^5$  
$ 1 \le K \le 10^5$  


**Sample Input**

	4
    2 4 
    3 4
    5 2
    1 10


**Sample Output**

	4
    13
    10
    1


**Explanation**

For the first testcase, the sequences are 
    
    (1,1,1,1), (1,1,1,2), (1,1,2,2), (1,2,2,2) = 4

For the second testcase, the sequences are 

    (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,2,2), (1,1,2,3), (1,1,3,3)
    (1,3,3,3), (1,2,2,2), (1,2,2,3), (1,2,3,3), (2,2,2,3), (2,2,3,3), (2,3,3,3)
    
which are 13 in number.  
    
For the third testcase, the sequences are  

    (1,1), (1,2), (1,3), (1,4), (1,5), (2,3), (2,5), (3, 4), (3, 5), (4, 5) = 10
    
for the fourth testcase, the only sequence is 

    (1,1,1,1,1,1,1,1,1,1)

Cod sursa

import sys

def primeSieve(n):
    A = [0, 0] + [1 for i in range(n - 1)]
    sqrtN = int(n ** 0.5)
    for i in range(2, sqrtN + 1):
        if A[i] == 1:
            for j in range(i * i, n + 1, i):
                A[j] = 0
    return [i for i, prime in enumerate(A) if prime]

def moebiusSieve(N):
    P = primeSieve(N + 1)
    Mu = [1] * (N + 1)
    Mu[0] = 0
    for p in P:
        for q in range(p, N + 1, p):
            Mu[q] *= -1
        for q in range(p * p, N + 1, p * p):
            Mu[q] = 0
    return Mu

def factAndInvFactTables(n, m):
    fact, invFact = [1] + n * [0], [1] + n * [0]
    for k in range(1, n + 1): 
        fact[k] = fact[k - 1] * k % m
    invFact[n] = pow(fact[n], m - 2, m)
    for k in range(n, 1, -1): invFact[k - 1] = invFact[k] * k % m
    return fact, invFact

MOD = 10 ** 9 + 7
mu = moebiusSieve(10 ** 5)
for t in range(int(sys.stdin.readline())):
    N, K = map(int, sys.stdin.readline().split())
    s = 0
    fact,invFact = factAndInvFactTables(N + K, MOD)
    for i in range(1, N + 1):
        s = (s + mu[i] * (fact[N // i + K - 1] * invFact[K] * invFact[N // i - 1]) % MOD) % MOD
    print(s)