[백준 24058] Coprime (python)

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

Coprime (서로소) 문제

n*k 이하의 자연수와 n의 서로소 들의 합을 구하는 문제

소수 개념과 포함 배제의 원리를 통해 해결할 수 있었다.

📌 문제 접근 포인트

1. N과 서로소인 것의 개수를 구해야하는데, 서로소의 정의상 두 정수를 나눌 수 있는 양의 정수가 1밖에 없다는 뜻은 소수들의 집합으로 비교하는 것을 의미한다. N 그 자체를 이용하기보단 N을 포함하고, N보다 작은 소수들을 이용해서 찾아서 계산해야한다.
2. 에라토스테네스의 체 개념을 이용해서 빠르게 소수를 구할 수 있게 구성해주자. 단순히 소수를 구하기만 해선 N의 값이 10**9에 해당하는 숫자이므로 시간이 오래걸릴 수 있다. 그렇기에 N의 크기를 작게 만들어서 연산을 진행 할 수 있게해주자.
3. 소수의 집합을 구했으면, 이제 소수를 이용해서 고를 수 있는 조합을 combination을 이용해서 뽑아주고, 거기서 뽑은 조합을 이용해 포함 배제의 원리대로 계산을 진행해주자.

4. 이때, 구한 서로소의 갯수를 m이라 하면, 서로소들의 합은 찾으려고 하는 수(n*k) *m / 2의 공식을 만족한다.

5. n>2 일경우 위 공식을 이용해서 출력해주자. n = 1일 경우에는 모든 수가 서로소에 해당하여 모든 수의 합을 구해주도록 조건을 나눠주면 해결 할 수 있었다.

⚙️ 내가 푼 정답코드

def primt(n): # 소수 구하기
    result = []
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            result.append(i)
            while n % i == 0:
                n //= i
    if n > 1:
        result.append(n)
    return result

from itertools import combinations
import sys
n, k = map(int, sys.stdin.readline().split())
m, result = n*k, n*k 
x = primt(n)
for i in range(1,len(x)+1):
    for comb in combinations(x,i): # 소수 조합에 대해서
        div = 1
        # 포함 배제의 원리로 서로수의 개수 구하기
        for j in comb:
            div *= j
        if i % 2 :
            result -= m//div
        else:
            result += m//div
if n == 1: # n == 1이면 그냥 모든 수의 합
    print(m*(m+1)//2)
else :
    print(result*m//2) # 서로수의 합 = 서로수의 개수 * 구하고자한 수 //2