[Python] 30510번 토마에 함수

https://www.acmicpc.net/problem/30510

30510번: 토마에 함수

---

 

24/03/07

 

 

이전에 SASA컵을 검수한 적이 있었다. 사실 그때 너무 바빴어서 풀이만 생각하고 정해 코드를 짜지 않았었는데, 이 문제의 해설을 작성해보고자 한다.

---

 

문제 접근 방식:

 

 

문제를 요약하면 다음과 같다.

 

• $x$가 무리수면 $f(x) = 0$
• $x$가 $0$이면 $f(x) = 1$
• 그 외 $x = \frac{p}{q} ; \mathrm{gcd}(p, q) = 1$이면 $f(x) = \frac{1}{q}$

임의의 유리수 $\frac{P}{Q}$가 주어질 때, $f(x) \geq \frac{P}{Q}$를 만족하는 $0$이상 $1$이하의 실수의 개수를 찾는 것이다.

 

먼저 가장 간단한 예시로, $P = Q$일 때의 경우를 살펴보자.

 

이 경우, $f(x) \geq 1$을 만족하는 실수 $x$를 $[0, 1]$구간에서 찾아야 한다.

 

이를 만족하는 실수 $x$는 $0$밖에 존재하지 않으므로, $1$개가 답이 된다.

 

$P < Q$일 때의 경우를 살펴보자.

 

그러면, $f(x) \geq \frac{P}{Q}$를 만족하는 실수 $x$를 $[0, 1]$구간에서 찾아야 한다.

 

이 조건을 만족하는 $x$는 무리수가 될 수 없다. 무리수인 경우에는 $f(x) = 0$이 되기 때문이다.

 

따라서 $x$가 임의의 유리수 $\frac{p_1}{q_1}$이라고 해보자. 여기서 $\mathrm{gcd}(p_1, q_1) = 1$이다.

 

그러면, $f(\frac{p_1}{q_1}) \geq \frac{P}{Q}$ $\Rightarrow$ $\frac{1}{q_1} \geq \frac{P}{Q}$ $\Rightarrow$ $q_1 \leq \frac{Q}{P}$이 된다.

 

예제 입력 1을 예시로 들어보면, $P = 3, Q = 11$이므로, $q_1 \leq \frac{11}{3}$을 만족시키는 $q_1$은 $1, 2, 3$으로 총 $3$가지가 있다.

 

이때, $q_1$은 분모에 해당하고, 그에 걸맞게 올 수 있는 분자 $p_1$은 $q_1$보다 작으면서 $\mathrm{gcd}(p_1, q_1) = 1$이어야 한다.

 

따라서, 그 개수는 서로소의 개수를 세는 함수인 오일러 파이 함수에 의하여 $\phi(1) + \phi(2) + \phi(3) = 4$개가 된다.

 

거기에 $0$은 항상 가능한 수이므로, $1$개를 더해주면 $5$개가 답이 되는 것이다.

 

즉, 이 문제를 해결하기 위해서는 $\frac{Q}{P}$보다 작거나 같은 모든 $x$에 대해서 오일러 파이 함수의 값을 모두 더해주고 거기에 $1$을 더해주면 된다.

 

처음에는 오일러 파이 함수의 합을 나타내는 함수를 따로 구현할 까 생각했지만, 그냥 오일러 파이 함수를 각 수마다 적용하는 방식으로 나이브하게 구현했다.

 

소수를 빠르게 판별하기 위해 에라토스테네스의 체를 부가적으로 사용했다.

 

또한 이전에 짜두었던 소인수 분해를 빠르게 하는 코드를 재활용하여 문제를 해결할 수 있었다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 30510번 토마에 함수
# 수학, 정수론, 오일러 파이 함수, sieve
'''
접근 방법:
P == Q인 경우
1개
그 외.(P < Q)
f(p1/q1) >= P/Q라고 하면
1/q1 >= P/Q
q1 <= Q/P
P = 3, Q = 11이라면
q1 <= 3
q1 = 1, 2, 3
phi(1) = 1, phi(2) = 1, phi(3) = 2 + 0
-> 답은 5
'''
sieve = [1 for _ in range(100_000+1)]
primes = []
sieve[0], sieve[1] = 0, 0 
for i in range(2, 317):
    if sieve[i]:
        for j in range(i*i, 100_000+1, i):
            sieve[j] = 0
for i in range(100_000+1):
    if sieve[i]:
        primes.append(i)
def factorization(a):
    if a == 1:
        return {}
    factors = dict()
    if sieve[a]:
        factors[a] = 1
        return factors
    prime = 2
    while prime*prime <= a:
        if a % prime == 0:
            factors[prime] = 0
            while a % prime == 0:
                a //= prime
                factors[prime] += 1
        else:
            prime += 1
    if sieve[a]:
        factors[a] = 1
    return factors
def euler_phi_function(N):
    if N == 1: return 1
    factors = factorization(N)
    phi = 1
    for prime, exp in factors.items():
        phi *= prime**(exp-1)
        phi *= (prime - 1)
    return phi
def solve():
    P, Q = map(int, input().split())
    N = Q//P
    s = 1
    for i in range(1, N+1):
        s += euler_phi_function(i)
    print(s)

solve()