포함 배제의 원리를 이용해 매우 큰 범위에서 조건에 맞는 수들만 빠르게 찾는 법 배우기 (+ 부분집합 구하기 재활)

1. 문제

 

9359번: 서로소 (acmicpc.net)

9359번: 서로소

 

2. 풀이

 

$10^{15}$이내에서 $N = 10^{9}$과 서로소인 수를 1초안에 찾으라고 한다면.. 보통의 방법으로는 찾기 힘들다

 

심지어 쿼리로 주어지니 더 어렵다

 

먼저 약수를 찾는 것보다 배수를 찾는 것이 쉽다는 것을 이해한다.

 

N의 소인수를 모두 찾고, N의 소인수의 배수는 N과 서로소가 아니므로, 이 방법을 이용해 서로소가 아닌 수들을 찾는다. 

 

범위 내에서 N과 서로소인 수와 서로소가 아닌 수로 나눌 수 있다.

 

따라서 범위 내의 모든 정수의 개수에서 N과 서로소가 아닌 수의 개수를 빼주면, N과 서로소인 수의 개수를 찾을 수 있다.

 

N의 소인수는 $O(\sqrt{N})$에 찾을 수 있다

 

여기서 N의 소인수의 지수는 찾지 말고, 소인수만을 찾는다.

 

p = 2

prime = []

while p*p <= n:

    count = 0

    while n % p == 0:

        n//=p
        count += 1

    if count >= 1:

        prime.append(p)

    p += 1

if n > 1:

    prime.append(n)

 

N의 소인수의 집합을 찾으면, 소인수의 부분집합을 모두 찾는다.

 

예를 들어 N = 2*3*5 = 30이면 {2}, {3}, {5}, {2,3}, {2,5}, {3,5}, {2,3,5}

 

각 부분집합의 모든 원소들의 곱이 N의 약수임을 이해한다.

 

즉, N의 약수는 2,3,5,6,10,15,30

 

1은 모든 수와 서로소니까 의미없어서 제외하고..

 

그래서 B이하에서 2,3,5,6,10,15,30의 배수들을 모두 제외하면, B이하에서 N과 서로소인 수의 집합이 된다.

 

먼저 B이하에서 2의 배수를 모두 찾는다. 이거는 B//2

 

3의 배수도 모두 찾으면 B//3, 5의 배수도 모두 찾으면 B//5

 

그러면 여기서 B - B//2 - B//3 - B//5

 

그런데, 6의 배수는 B이하에서 B//6개인데... 문제는 여기에는 2의 배수도 있고 3의 배수도 있다.

 

그러니까 6의 배수는 2의 배수와 3의 배수의 교집합이다. 

 

B//2와 B//3을 빼면서 6의 배수가 2번 빼졌다. 그러니까 B//6을 더해서, 2번 빼진것을 보상해준다

 

B - B//2 - B//3 - B//5 + B//6

 

나머지, 10의 배수와 15의 배수도 각각 2,5의 배수의 교집합, 3,5의 배수의 교집합이므로...

 

B - B//2 - B//3 - B//5 + B//6 + B//10 + B//15

 

마지막 30의 배수는 2,3,5의 배수의 교집합이다.

 

2의 배수, 3의 배수, 5의 배수를 빼면서 3번 빼지고, 6의 배수, 10의 배수, 15의 배수를 빼면서 3번 더해져서...

 

30의 배수는 아직 안빼졌다. 그래서 B - B//2 - B//3 - B//5 + B//6 + B//10 +B//15 - B//30

 

이거 어디서 본것 같은데..?

 

포함과 배제의 원리(include - exclude principle)이다

 

$$\left| \bigcup A_{i} \right| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{I \in \binom{(1,2,...,n)}{k}} \left| \bigcap_{i \in I} A_{i} \right|$$

 

유한 부분집합들의 합집합의 원소의 개수를 세는 방법을 알려주는 공식..

 

증명은 수학적 귀납법으로 가능한데 생략하고

 

포함-배제 원리의 세 가지 증명 – I Seul Bee

포함-배제 원리의 세 가지 증명 – I Seul Bee

 

https://blog.myungwoo.kr/51

포함-배제의 원리

 

핵심은 $$\left| A \cup B \right| = \left| A \right| + \left| B \right| - \left| A \cap B \right|$$이랑

 

$$\left| A \cup B \cup C \right| = \left| A \right| + \left| B \right| + \left| C \right| - \left|A \cap B \right| -\left|A \cap C \right| - \left| B \cap C \right| + \left| A \cap B \cap C \right|$$

 

집합이 홀수개들의 교집합일때는 더해주고, 짝수개들의 교집합일때는 빼주고만 기억하면 구현은 쉽다

 

그런데 부분집합을 구하는 방법이 이게 기억이 안난다

 

https://deepdata.tistory.com/428

바이너리 카운팅을 이용한 부분집합 구현과 재귀함수를 이용한 조합 구현하기

 

p = len(prime)

for i in range(1<<p):

    partial = []

    for j in range(p):

        if i & (1 << j):

            partial.append(prime[j])

 

모든 부분집합들을 찾아 부분집합 원소들의 곱을 구하고, 해당 곱의 범위 내에서 배수를 구해준다.

 

부분집합의 크기가 짝수개이면 누적으로 빼주고 홀수개이면 누적으로 더해줘서 N과 서로소가 아닌 수들의 집합의 크기를 구해준다. 

 

주의할 점은 이 방법에서 partial이 []으로 공집합이 나올수 있는데 이거는 의미없으니까 빼준다

 

마지막으로, [B - (B 이내에서 N과 서로소가 아닌 수들의 개수)] - [A-1 - (A-1 이내에서 N과 서로소가 아닌 수들의 개수)] = [A이상 B이내에서 N과 서로소인 수들의 개수]가 될 것이다.

 

부분집합을 찾는 연산은 2*3*5*7*11*13*17*19*23*29가 $10^{9}$ 이하라서, 많아야 $O(2^{10}) = O(10^{3})$정도이다.

 

쿼리가 최악으로 $O(10^{2})$이라, $O(10^{6} + 10^{5})$ 정도에 문제를 해결할 수 있다

 

from sys import stdin

T = int(stdin.readline())

for t in range(T):
    
    a,b,n = map(int,stdin.readline().split())
        
    p = 2

    answer1 = 0 #1 ~ B 이하에서 N과 서로소가 아닌 수들의 개수
    answer2 = 0 #1 ~ A-1 이하에서 N과 서로소가 아닌 수들의 개수
    
    #N의 모든 소인수를 찾는다
    prime = []

    while p*p <= n:
        
        count = 0

        while n % p == 0:
            
            n//=p
            count += 1
        
        if count >= 1:
            
            prime.append(p)
        
        p += 1
    
    if n > 1:
        
        prime.append(n)
    
    #N의 소인수들의 집합에 대한 모든 부분집합을 찾는다
    p = len(prime)

    for i in range(1<<p):
        
        partial = []

        x = 0

        for j in range(p):
            
            if i & (1 << j):
                
                partial.append(prime[j])
                x += 1
        
        #포함과 배제의 원리
        
        #공집합은 제외하고,
        if x == 0:
            
            continue
        
        #부분집합의 크기가 짝수이면,
        if x % 2 == 0:
            
            #원소들의 곱을 빼준다
            y = 1

            for k in partial:
                
                y *= k

            answer1 -= b//y
            answer2 -= (a-1)//y
        
        #부분집합의 크기가 홀수이면
        else:
            
            #원소들의 곱을 더해준다
            y = 1

            for k in partial:
                
                y*= k
            
            answer1 += b//y
            answer2 += (a-1)//y
    
    #[A이상 B이하에서 N과 서로소인 수들의 개수]
    # = [A이상 B이하의 개수] - [B 이하에서 N과 서로소가 아닌 수들의 개수] - [A-1이하에서 N과 서로소가 아닌 수들의 개수]
    print(f'Case #{t+1}: {b - a + 1 - answer1 + answer2}')