Relatively Prime Powers (Codeforces 1036F)
Tags: Math, combinatorics

Consider some positive integer $$$x$$$. Its prime factorization will be of form $$$x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots$$$Let's call $$$x$$$ elegant if the greatest common divisor of the sequence $$$k_1, k_2, \dots$$$ is equal to $$$1$$$. For example, numbers $$$5 = 5^1$$$, $$$12 = 2^2 \cdot 3$$$, $$$72 = 2^3 \cdot 3^2$$$ are elegant and numbers $$$8 = 2^3$$$ ($$$GCD = 3$$$), $$$2500 = 2^2 \cdot 5^4$$$ ($$$GCD = 2$$$) are not.Count the number of elegant integers from $$$2$$$ to $$$n$$$.Each testcase contains several values of $$$n$$$, for each of them you are required to solve the problem separately.

Input: The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of values of $$$n$$$ in the testcase.Each of the next $$$T$$$ lines contains a single integer $$$n_i$$$ ($$$2 \le n_i \le 10^{18}$$$).

Output: Print $$$T$$$ lines — the $$$i$$$-th line should contain the number of elegant numbers from $$$2$$$ to $$$n_i$$$.

Note: Here is the list of non-elegant numbers up to $$$10$$$:  $$$4 = 2^2, GCD = 2$$$;  $$$8 = 2^3, GCD = 3$$$;  $$$9 = 3^2, GCD = 2$$$. The rest have $$$GCD = 1$$$.

Sample Inputs:
4
4
2
72
10

Sample Outputs:
2
1
61
6

Solution (Python):
from math import sqrt, log2
from sys import stdin
from bisect import bisect
import time

def all_primes(n):
    res = []
    for i in range(1, n + 1):
        prime = True
        for j in range(2, min(int(sqrt(i)) + 2, i)):
            if i % j == 0:
                prime = False
                break
        if prime:
            res.append(i)
    return res

def count_pow_nums(n, p):
    top = int(pow(n, 1.0 / p))
    if pow(top + 2, p) <= n:
        return top + 1
    elif pow(top + 1, p) <= n:
        return top
    elif pow(top, p) <= n:
        return top - 1
    else:
        return top - 2
primes = all_primes(64)
num_set = set()
max_n = 1000000000000000000
for pi in range(3, len(primes)):
    p = primes[pi]
    cnt = count_pow_nums(max_n, p)
    for n in range(2, cnt + 5):
        sq2 = round(sqrt(n))
        sq3 = round(pow(n, 1 / 3))
        if sq2 ** 2 != n and sq3 ** 3 != n:
            num = pow(n, p)
            if num <= max_n:
                num_set.add(num)
nums = sorted(num_set)
t = int(stdin.readline())
for i in range(t):
    n = int(stdin.readline())
    ans = n - 1 - count_pow_nums(n, 2) - count_pow_nums(n, 3) + count_pow_nums(n, 6)
    ans -= bisect(nums, n)
    print(ans)

Solution (Python):
import bisect
import math
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def the_sieve_of_eratosthenes(n):
    s = [1] * (n + 1)
    x = []
    for i in range(2, n + 1):
        if s[i]:
            x.append(i)
            for j in range(i, n + 1, i):
                s[j] = 0
    return x
t = int(input())
ans = []
x = the_sieve_of_eratosthenes(64)
s = set()
s2 = set()
for i in range(2, pow(10, 6) + 5):
    s2.add(i * i)
inf = pow(10, 18)
for i in x[1:]:
    j = 2
    while True:
        y = pow(j, i)
        if y > inf:
            break
        c = max(int(math.sqrt(y)) - 3, 1)
        while pow(c, 2) < y:
            c += 1
        if pow(c, 2) ^ y:
            s.add(y)
        j += 1
s = list(s)
s.sort()
for _ in range(t):
    n = int(input())
    ng = 0
    c = max(int(math.sqrt(n)) - 3, 1)
    while pow(c, 2) <= n:
        c += 1
    ng = c - 2 + bisect.bisect_right(s, n)
    ans0 = n - ng - 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
def intrt(n, p):
    L = 1
    R = n
    while R > L + 1:
        M = (L + R) // 2
        if M ** p > n:
            R = M
        else:
            L = M
    if R ** p <= n:
        return R
    return L

def intsqrt(n):
    L = 1
    R = n
    while R > L + 1:
        M = (L + R) // 2
        if M * M > n:
            R = M
        else:
            L = M
    if R * R <= n:
        return R
    return L
Nlen = int(input())
N = [int(input()) for _ in range(Nlen)]
N = sorted([[N[i], i] for i in range(Nlen)], reverse=1)
ans = [0] * Nlen
R = 60
a = [None] + [intrt(10 ** 18, i) for i in range(1, R + 1)]
for I in range(Nlen):
    n = N[I][0]
    a[1] = n
    a[2] = intsqrt(n)
    for i in range(3, R):
        while a[i] ** i > n:
            a[i] -= 1
    b = [0] * (R + 1)
    for i in range(R, 0, -1):
        b[i] = a[i]
        j = 2 * i
        while j <= R:
            b[i] -= b[j]
            j += i
    ans[N[I][1]] = b[1] + 1
for e in ans:
    print(e)