HackerRank Number Theory – Coprime Conundrum

Challenge: Coprime Conundrum

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464753486

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/arthur-and-coprimes/problem

Cerinta

Arthur defines a function, $f(k)$, to be the number of $(p, q)$ pairs such that:

* $1 \lt p \le q \le k$
* $p$ and $q$ are [coprime](https://en.wikipedia.org/wiki/Coprime_integers).
* $p \cdot q = k$


Given an integer, $n$, help Arthur find and print the result of: 
$$\sum_{k = 1}^{n} f(k)$$

Input Format

The first line contains a single integer denoting $n$.

Output Format

Print the result of $\sum_{k = 1}^{n} f(k)$ on a new line.

Constraints

* $ 1 \le n \le 10^9$

**Subtasks**

* $ 1 \le n \le 150$ for $\text{30%}$ of the maximum score.
* $ 1 \le n \le 10^6$ for $\text{60%}$ of the maximum score.

Cod sursa

#!/bin/python3

import math
import sys


def solve(n: int) -> int:
    lim = int(math.isqrt(n))

    spf = list(range(lim + 1))
    for i in range(2, int(math.isqrt(lim)) + 1):
        if spf[i] == i:
            step = i
            start = i * i
            for j in range(start, lim + 1, step):
                if spf[j] == j:
                    spf[j] = i

    uniq_cache = [[] for _ in range(lim + 1)]

    for x in range(2, lim + 1):
        v = x
        ps = []
        while v > 1:
            p = spf[v]
            ps.append(p)
            while v % p == 0:
                v //= p
        uniq_cache[x] = ps

    def coprime_count(m: int, p: int) -> int:
        # Count 1 <= q <= m with gcd(q, p) = 1.
        if m <= 0:
            return 0
        ps = uniq_cache[p]
        k = len(ps)
        ans = 0
        for mask in range(1 << k):
            d = 1
            bits = 0
            for i in range(k):
                if (mask >> i) & 1:
                    d *= ps[i]
                    bits += 1
            t = m // d
            if bits & 1:
                ans -= t
            else:
                ans += t
        return ans

    total = 0
    for p in range(2, lim + 1):
        m = n // p
        if m < p:
            break
        # q in [p..m], gcd(p,q)=1
        # gcd(p,p) != 1 for p > 1, so using <=p is safe.
        total += coprime_count(m, p) - coprime_count(p, p)

    return total


def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    print(solve(n))


if __name__ == '__main__':
    main()