Soluție HackerRank pentru GCD Sequence, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: GCD Sequence
  • Domeniu: Number Theory
  • Limbaj: Python 3

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

Cerință

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, ·s 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.

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 ≤ T ≤ 5
1 ≤ N ≤ 10^5
1 ≤ K ≤ 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 sursă

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)
HackerRank Number Theory – GCD Sequence