AtCoder Beginner Contest 361 F - x = a^b

ABC361의 모든 문제 중 가장 짧고 가장 이해하기 쉬운 문제였으나 간단한 설명과 달리 꽤나 치밀한 아이디어가 필요했고 그걸 떠올리는 과정이 재밌어서 정리를 남겨본다.

시간 제한	메모리 제한
2초	1024MB

문제

1이상 N이하의 정수 x에 대하여 어떤 정수 a와 2이상의 정수 b로 x = a^b로 표현 가능한 것은 얼마나 있는가?

 

입력

입력은 아래 형식의 표준입력으로 주어진다.

N

 

조건

• 입력은 전부 정수이다.
• 1 ≤ N ≤10¹⁸

출력

답을 정수로 출력하시오.

 

입력예1

99

 

출력예1

12

문제의 조건을 만족하는 정수는 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81으로 12개다.

 

입력예2

1000000000000000000

 

출력예2

1001003332

 

---

풀이

조건에 맞는 정수인 a의 b거듭제곱 꼴로 나타내어지는 x는 어떤 규칙이 있을까? 가능한 수들을 작은 것 부터 쭉 나열해보자.

1 = 1²
4 = 2²
8 = 2³
9 = 3²
16 = 2⁴ = 4²
25 = 5²
27 = 3³
32 = 2⁵
36 = 6²
49 = 7²
64 = 2⁶ = 4³ = 8²
81 = 3⁴ = 9²
...

입력예 1에 나온 12개 정수들을 x = a^b로 표현해보면 이런 규칙을 찾을 수 있다. a에는 1부터 모든 정수가 들어갈 수 있다. b에는 16, 64, 81과 같이 더 작은 a의 거듭제곱으로 나타낼 수 있는 경우를 제외하고 모두 소수가 들어가고 있다. 노란색은 2, 주황색은 3, 빨간색은 5다.

 

떠오른 가설은 a에 대한 거듭제곱의 결과가 N을 넘지 않는 b의 소수 번호가 a로 만들 수 있는 x의 가짓수라는 것이다. b가 소수가 아닌 경우, 지수법칙으로 b의 소인수 거듭제곱 형태를 만들어버리면 결국 소수 지수를 갖는 x가 되는 것이다.

x = a^b (b는 소수 b'과 b''으로 이루어진 합성수)
x = a^b = a^(b'*b'') = (a^b')^b'' = (a^b'')^b'

 

이렇게 a의 b거듭제곱 형태라면 지수법칙에 따라 b가 소수가 아닐 때 b를 약수로 나누어 다른 a로 표현하는 게 가능하다. 따라서 모든 정수 a에 대해 소수인 b의 거듭제곱으로만 표현되는 경우를 살펴보자.

b	얻을 수 있는 x값
2	1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, ...
3	1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096, ...
5	1, 32, 243, 1024, 3125, 7776, 16807, 32768, 59049, 100000, ...
...

이렇게 소수 b에 따라 만들어지는 x값이 얻어진다. N이 99라면 연두색으로 색칠된 부분만 보면 된다. 저기서 겹치는 숫자를 제거하면 모든 x를 찾을 수 있다.

a\b	2	3	5	7	11	13	17	19	...
1	1	1	1	1	1	1	1	1	...
2	4	8	32	128	2048	8192	131072	524288	...
3	9	27	243	2187	177147	1594323	...	...	...
4	16	64	1024	16384	494304	...	...	...	...
5	25	125	3125	78125	...	...	...	...	...
6	36	216	7776	279936	...	...	...	...	...
7	49	343	16807	...	...	...	...	...	...
8	64	512	32768	...	...	...	...	...	...
...	...	...	...	...	...	...	...	...	...

겹치는 겹치는 경우만 따로 살펴보면

4³ = 8² = 2⁶ = 2^(2*3)
4⁵ = 32² = 2¹⁰ = 2^(2*5)
8⁵ = 32³ = 2¹⁵ = 2^(3*5)

지수가 서로 다른 소수의 곱으로 이루어진 합성수의 경우는 이렇게 겹치게 된다. 당연히 세 소수의 곱으로 이루어진 경우도 여기서 또 겹친다. 이제 찾아야 하는 x들을 정리해보면

1. 2부터 정수 a에 대해 소수 거듭제곱의 결과가 N을 넘지 않는 최대의 b를 찾는다.(1은 나중에 1가지로 더해주면 끝)
2. b의 소수 번호를 확인하고 번호를 경우의 수에 합한다.(ex. prime[1] = 2, prime[2] = 3, prime[8] = 19)

여기에서 최대의 b를 찾는 과정이 거듭제곱을 계속 해나가며 N이 넘는지 확인하는 복잡한 연산이기 때문에 두 가지 테크닉을 더한다. 거듭제곱은 분할정복을 통한 빠른 거듭제곱으로, 최대의 b 찾기는 이분탐색으로.

 

그리고 소수 2개의 곱으로 나타내어진 b의 경우는 여기서 겹쳐버리기 때문에 제거해야 한다. 소수 2개의 곱으로 만들어지는 prime2를 만들어 같은 방법으로 경우의 수를 찾아 중복을 제거한다.

 

마지막으로 소수 3개의 곱으로 나타내어진 b는 이전 단계에서 두 번씩 제거되어버렸기 때문에 다시 찾아서 더해줘야한다. prime3를 만들어 같은 방법으로 경우의 수를 찾아 더해준다.

 

정답 코드

N = int(input())
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
prime2 = []
prime3 = []
for i in range(17):
    for j in range(i+1,17):
        prime2.append(prime[i]*prime[j])
        for k in range(j+1,17):
            prime3.append(prime2[-1]*prime[k])
prime2.sort()
prime3.sort()

def fexp(n,k):
    res = 1
    while k > 0:
        if k&1:
            res *= n
        n *= n
        k >>= 1
    return res

count = 1

for p in prime:
    s,e = 2,N+1
    while s < e:
        m = (s+e)//2
        t = fexp(m,p)
        if t>N:
            e = m
        else:
            s = m+1
    while fexp(s,p) > N: s -= 1
    if s > 0: s -= 1
    if s == 0: break
    count += s

for p in prime2:
    s,e = 2,N+1
    while s < e:
        m = (s+e)//2
        t = fexp(m,p)
        if t>N:
            e = m
        else:
            s = m+1
    while fexp(s,p) > N: s -= 1
    if s > 0: s -= 1
    if s == 0: break
    count -= s

for p in prime3:
    s,e = 2,N+1
    while s < e:
        m = (s+e)//2
        t = fexp(m,p)
        if t>N:
            e = m
        else:
            s = m+1
    while fexp(s,p) > N: s -= 1
    if s > 0: s -= 1
    if s == 0: break
    count += s

print(count)