백준 30510 토마에함수

문제

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

30510번: 토마에 함수

 

P<=Q이므로 0과 1을 넣는다면 무조건 답을 만족한다.

나머지 수들을 생각해보자. 무리수의 정의는 두 정수의 비로 나타낼 수 없는 수이다. 따라서 x를 X/Y로 생각해보자.(0<X<Y)

f(X/Y) = 1/Y고 1/Y >= P/Q -> Q >= P * Y를 만족해야한다.

따라서 양의정수 Y는 최악의 상황에도 P,Q 입력범위인 10만을 넘지 않는다. Y범위가 정해졌으므로 자동으로 X범위도 정해진다.(0과 Y를 포함안한 이뉴는 0과1은 무조건 답이기에 중복을 제거하기 위함이다.)

 

이제 해야할 작업은 어떤 Y에 대해 X/Y가 기약분수가 되는 모든 X를 찾는 것이다. 기약분수가 아니라면 중복케이스가 생긴다.

X/Y가 기약분수가 되려면, X는 Y의 어떤 소인수로도 나눠 떨어지면 안된다.

브루트포싱은 시간초과일테고, 1부터 Y-1까지 수중에서 Y의 소인수로 나누어 떨어지는 수들의 갯수를 찾고 뺴는 것이 적절해보인다.

Y는 1부터 Q까지 가능하므로 각 Y를 소인수분해하는데 O(10만sqrt(10만))복잡도이므로 충분히 가능한 효율성이다.

 

이제 빼야할 수를 찾는 방법이 문제인데, 유형화돼있는 조합론 문제이다.

M(c)를 어떤 조합 c의 원소를 모두 곱한 값이라하자.

어떤 수 범위에서 소수집합 P의 모든 원소에게 나누어 떨어지지 않는 수의 갯수는

어떤 수의 갯수에다가

1. P에서 원소 홀수개(1,3,5,..)를 선택한 조합C의 모든 M(C)값을 다 뺴주고

2. P에서 원소 짝수개(2,4,6,..)를 선택한 조합C의 모든 M(C)값을 다 더해준다.

 

증명

특정 수의 소인수 집합의 크기가 n이다.

특정 수는 당연히 1번만 뺴야한다. 즉 결과값은 -1이다.

이향계수 성질에 의해 

nC0 + nC2 + nC4 + ... = 2^(n-1)이다.

nC1 + nC3 + nC5 + ... = 2^(n-1)이다.

아무것도 선택하는 경우의 수는 없으므로 nC0 = 1은 제외한다.

nC2 + nC4 + ... - (nC1 + nC3 + nC5 + ...) = 2^(n-1) - 1 - 2^(n-1) = -1이다. 

 

복잡도

100000만이하의 수중 가장 많은 소인수 개수를 직접 코드를 돌려 구할 수 있다. 6개정도 될 것이다.

6개 가지고 조합돌려봐야 얼마안된다..상수취급하자. (64)

 

 

 

코드

from itertools import combinations
def facto(x):
    r = set([])
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            r.add(i)
            while x % i == 0:
                x = x // i
    if x != 1:
        r.add(x)
    return r


ans = 2 
for par in range(2, 111111):
    if P * par > Q:
        break
    f = list(facto(par))
    state = -1
    bias = 0
    for cnt in range(1, len(f) + 1):
        for combi in combinations(f, cnt):
            tmp = 1
            for c in combi:
                tmp = tmp * c
            bias += state * ((par - 1) // tmp)
        state = state * -1
    ans += par - 1 + bias
print(ans)

조합 or 순열구하는건 무지성 파이썬이 최고다.