알고리즘 - Python / 백준 - 13926번 : gcd(n, k) = 1

13926번: gcd(n, k) = 1 (acmicpc.net)

13926번: gcd(n, k) = 1

 

---

풀이

• 자연수 n이 주어졌을 때 , n보다 작고 gcd(n,k) = 1을 만족하는 자연수 k의 개수를 구하는 문제다.
• gcd(a,b)는 a와 b의 최대공약수를 의미하고 이 최대 공약수가 1이라는 뜻은 두 수가 서로소라는 뜻이다.
• 그러면 어떠한 수 n과 1 ~ n 까지의 k가 서로소인지 아닌지 판별해야 한다.
• 이때 , 다음과 같은 과정을 통해 알아낼 수 있다.
• 1. 어떠한 수 n을 소인수 분해 한다.
• 2. n을 소인수 분해한 수들이 p1,p2,p3.... pi 일 때 , k와 n이 서로소인지 알아보는 방법은 k가 모든 p에 대해 나누었을 때 , 나머지가 0이 아니면 된다.
• 3. 이러한 수들의 개수를 모아서 출력하면 된다.

 

풀이 1번

• 어떠한 수 n을 소인수분해 해야 하는데 n의 범위가 최대 10^18 이다.
• 이 경우 일반적인 소인수분해 알고리즘을 사용할 수 없다.
• 이전에 사용한 큰 수를 소인수분해 하는 폴라드 로 알고리즘과 밀러 라빈 소수 판별법을 사용해 소인수 분해한다.
• 이와 관련된 내용은 아래 링크들을 참고하자.

 

 

알고리즘 - Python / 백준 - 4149번 : 큰 수 소인수분해 (tistory.com)

알고리즘 - Python / 백준 - 4149번 : 큰 수 소인수분해

 

 

 

폴라드 로 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

폴라드 로 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

 

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

밀러-라빈 소수판별법 - 위키백과, 우리 모두의 백과사전

 

 

 

풀이 2번 , 3번

• 이제 10^18 범위 내의 수들을 소인수 분해하여 p1,p2,p3...pi 들을 구했다.
• 이 p배열을 통해 0 ~ n 사이의 수들이 이 pi로 나누어 떨어지는지 확인하고 , 모든 pi에 대해 나누어 떨어지지 않을 때 gcd(n,k) = 1 을 만족하는 , 즉 서로소 라는 것을 알 수 있다.

 

 

구현 1번

• 처음 이 아이디어를 가지고 구현할 때는 어떠한 수 k에 대해 모든 pi를 가지고 반복문을 돌려 나머지 연산을 진행하고 모든 pi로 나눈 나머지가 0이 아닌 경우에 정답을 1씩 늘려주는 방식으로 구현하였다.
• 이렇게 구현하니 어느 정도 큰 수를 입력하니 시간이 너무 오래 걸렸다.
• 일일이 모든 k를 모든 pi에 대해 나누는 것이 문제가 있다고 생각하고 다른 풀이를 생각해 보았다. 

 

 

구현 2번

• 감이 안 잡힐 때는 언제나 예시를 가지고 살펴본다.
• 먼저 10의 예시를 가지고 살펴보았다. 

 

 

• 10의 소인수인 2와 5를 가지고 1 ~ 10 사이의 수들을 나누었을 때 나머지를 정리한 표다.
• 10의 경우 정답은 한 번도 나머지가 0이 나오지 않은 [1,3,7,9]가 될 것이다.
• 이 표를 정리하고 나니 다음과 같은 특징이 보인다.
• 1 ~ 10 사이에 2로 나누었을 때 나머지가 0이 나오는 수들의 개수는 10 / 2 = 5개 이고 , 5로 나누었을 때 나머지가 0이 나오는 수들의 개수는 10 / 5 = 2 개이다.
• 그렇다면 전체 10개 중에서 0이 한 번도 안 나온 것들의 수니까 각각의 소인수들에 대해 0이 등장한 횟수 ( 2는 5개 , 5는 2개 )를 빼주면 답이 나올 것이라 생각했다.
• 당연하게도 2와 5에서 2번 빼준 10은 1번 빼는 것이 맞으므로 +1을 해주어 보정해준다.
• 정리하면 10 - 5 - 2 + 1 = 4로 정답이 나오게 된다.
• 이를 일반화하여 2,3,5를 인수로 갖는 30에 대해서도 생각해보니 위의 예상이 맞았다.

 

 

N = 30 의 예시

• 30의 경우 소수가 2,3,5 이므로 30 / 2 = 15 , 30 / 3 = 10 , 30 / 5 = 6이다.
• 일단 중복 생각 안 하고 전체 30개에서 15 , 10 , 6 개를 빼주니 -1이다.
• 중복을 고려해야 하니 (2,3 = 6) , (2,5 = 10) , (3,5 = 15)를 30에서 나누어 준다.
• 30 / 6 = 5 , 30 / 10 = 3 , 30 / 15 = 2 이므로 다시 -1에서 +5 +3 + 2를 해준다.
• 왜냐하면 6의 배수 , 10의 배수 , 15의 배수들은 이미 위에서 겹쳐져서 2번 빼준 것들 이기 떄문에 +1 씩 해주는 것이다.
• 그러면 또 6 , 10 , 15 의 공배수는 또 여러번 더해준 상태가 되니 이부분을 제거 해야한다.
• 예를 들어 30의 경우 , 6 , 10 , 15 의 배수면 +1 하기로 했으니 6에서 , 10에서 , 15에서 각각 +1이 3번 되었을 것이다.
• 그렇기에 주어진 소인수들로 만들 수 있는 모든 조합에 대해서 보정해주어야 한다.
• 즉 이전단계에 보정을 더해주었으니 마지막 2,3,5를 모두 사용한 30 / 30 = 1 은 빼주어야 한다는 뜻이 된다.
• 위의 예시를 천천히 읽으면 바로 소인수들의 조합으로 체크할 수를 만들 때 , 사용한 소인수의 개수가 홀수면 n에서 빼주고 , 짝수면 더해주면 된다는 사실을 알 수 있다.
• 이를 통해 나누어서 0이 한번이라도 나온 수들의 개수를 중복을 제외하고 셀 수 있다는 것이다.
• 마무리를 내자면 (2,3,5 = 30)이고 이는 소인수 3개 즉 홀수 개수로 만들었으므로 빼주어야 한다.
• 따라서 N = 30의 답은 9 - 1 = 8로 나오게 된다.

 

 

 

 

import sys

def powmod(a,b,m):
    result = 1
    while b > 0:
        if b % 2 != 0:
            result = (result * a) % m
        b //= 2
        a = (a * a) % m

    return result

def mr(n,a):
    r = 0
    d = n-1
    while (d%2 == 0):
        r += 1
        d = d // 2
    x = powmod(a,d,n)
    if x == 1 or x == n-1:
        return True
    for i in range(0,r-1):
        x = powmod(x,2,n)
        if x == n-1:
            return True
    return False

def check_prime(k):
    check = 0
    if k <= 71:
        if k in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]:
            return True
        else:
            return False
    else:
        for i in [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
            if mr(k,i) == False:
                break
            else:
                check += 1
        if check == 12:
            return True
        else:
            return False

n = int(sys.stdin.readline())
ori_n = n

def gcd(a, b):
    if b > a:
        k = a
        a = b
        b = k
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

def g(x,n):
    return ((x*x) + 1) % n


def pola(n,x):
    p = x
    if check_prime(n):
        return n
    else:
        for i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]:
            if n % i == 0:
                return i
        y = x
        d = 1
        while d == 1:
            x = g(x,n)
            y = g(g(y,n),n)
            d = gcd(abs(x-y),n)
        if d == n:
            return pola(n,p+1)
        else:
            if check_prime(d):
                return d
            else:
                return pola(d,2)
ans = []
while n != 1:
    k = pola(n,2)
    ans.append(int(k))
    n = n // k

from itertools import combinations

check_sum = ori_n
ans = list(set(ans))
for i in range(1,len(ans)+1):
    for t in combinations(ans,i):
        k = 1
        for p in t:
            k *= p
        if i % 2 == 1:
            check_sum -= (ori_n // k)
        else:
            check_sum += (ori_n // k)

if ori_n == 1:
    print(1)
else:
    print(check_sum)

 

---