Sad powers (Codeforces 955C)
Tags: Math, number theory

You're given Q queries of the form (L, R). For each query you have to find the number of such x that L ≤ x ≤ R and there exist integer numbers a > 0, p > 1 such that x = ap.

Input: The first line contains the number of queries Q (1 ≤ Q ≤ 105).The next Q lines contains two integers L, R each (1 ≤ L ≤ R ≤ 1018).

Output: Output Q lines — the answers to the queries.

Note: In query one the suitable numbers are 1 and 4. 

Sample Inputs:
6
1 4
9 9
5 7
12 29
137 591
1 1000000

Sample Outputs:
2
1
0
3
17
1111

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
J = set()
for i in range(2000):
    J.add(i ** 2)
    J.add(i ** 3)
Ri = set()
for p in range(5, 61, 2):
    if p % 3 == 0:
        continue
    for base in range(2, 10 ** 9):
        if base in J:
            continue
        bp = pow(base, p)
        if bp > 10 ** 18:
            break
        Ri.add(bp)
Ri = list(Ri)
Ri.sort()
LL = len(Ri)

def calc(x):
    res = 0
    ng = 10 ** 9 + 1
    ok = 0
    while abs(ok - ng) > 1:
        med = (ok + ng) // 2
        if med * med <= x:
            ok = med
        else:
            ng = med
    res += ok
    ng = 10 ** 6 + 1
    ok = 0
    while abs(ok - ng) > 1:
        med = (ok + ng) // 2
        if med * med * med <= x:
            ok = med
        else:
            ng = med
    res += ok
    ng = 10 ** 3 + 1
    ok = 0
    while abs(ok - ng) > 1:
        med = (ok + ng) // 2
        if med * med * med * med * med * med <= x:
            ok = med
        else:
            ng = med
    res -= ok
    ng = LL
    ok = -1
    while abs(ok - ng) > 1:
        med = (ok + ng) // 2
        if Ri[med] <= x:
            ok = med
        else:
            ng = med
    res += ok + 1
    return res
Q = int(readline())
Ans = [None] * Q
for qu in range(Q):
    (L, R) = map(int, readline().split())
    Ans[qu] = calc(R) - calc(L - 1)
print('\n'.join(map(str, Ans)))

Solution (Python):
import sys
import math
from math import sqrt
import bisect
small = 10 ** 5 + 1
big = 10 ** 18 + 1
pos = []
f = pos.append
j = 2
while True:
    j2 = j * j
    i = j * j2
    if i >= big:
        break
    while i < big:
        f(i)
        i *= j2
    j += 1
pos2 = [p for p in pos if not sqrt(p).is_integer()]
pos2.sort()
prev = -1
pos = []
f = pos.append
for p in pos2:
    if p == prev:
        continue
    f(p)
    prev = p
q = int(input())
out = []
for line in sys.stdin:
    (L, R) = line.split()
    L = int(L)
    R = int(R)
    a = -1
    b = len(pos)
    while b - a > 1:
        m = (a + b) // 2
        if pos[m] < L:
            a = m
        else:
            b = m
    under = a
    a = -1
    b = len(pos)
    while b - a > 1:
        m = (a + b) // 2
        if pos[m] <= R:
            a = m
        else:
            b = m
    upper = a
    Lupp = max(int(sqrt(L) - 1), 0)
    while Lupp * Lupp < L:
        Lupp += 1
    Rdown = int(sqrt(R)) + 1
    while Rdown * Rdown > R:
        Rdown -= 1
    count = max(0, Rdown - Lupp + 1)
    out.append(str(upper - under + count))
print('\n'.join(out))

Solution (Python):
import math
import bisect
import sys

def flrt(exp, x):
    l = max(0, math.floor(x ** (1 / exp)) - 3)
    r = math.floor(x ** (1 / exp)) + 3
    while l < r:
        mid = (l + r) // 2
        if mid ** exp <= x:
            l = mid + 1
        else:
            r = mid
    return l - 1

def c1(r):
    ans = set()
    pr = [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
    for i in pr:
        x = 2
        while x ** i <= r:
            val = x ** i
            b2 = flrt(2, val)
            b3 = flrt(3, val)
            if b2 ** 2 != val and b3 ** 3 != val:
                ans.add(val)
            x += 1
    return ans

def solve(r, pc):
    if r == 0:
        return 0
    a = [2, 3]
    ans = 0
    for i in range(1, 2 ** len(a)):
        tot = 0
        mult = 1
        for (j, x) in enumerate(a):
            if i & 1 << j:
                mult *= x
                tot += 1
        d = flrt(mult, r)
        ans += d if tot % 2 else -d
    return ans + bisect.bisect_right(pc, r)
    lp = 0
    rp = len(pc)
    while lp < rp:
        mid = (lp + rp) // 2
        if pc[mid] <= r:
            lp = mid + 1
        else:
            rp = mid
    return ans + lp
q = int(input())
pc = c1(1e+18 + 1)
pca = list(pc)
pca.sort()
for i in range(q):
    (l, r) = [int(x) for x in sys.stdin.readline().split()]
    ans = solve(r, pca) - solve(l - 1, pca)
    sys.stdout.write(str(ans) + '\n')