코드노예

모듈로 연산에서 역수는 다음과 같습니다.

두 정수 a와 m 에 대해서, a의 m에 대한 모듈러 역수 x는 a에 x를 곱해서 m으로 나눈 나머지가 1이 되는 값을 찾으면 됩니다. 이 때 x는 m보다 작은 양의 정수 입니다.

 a * x ~= 1 (mod m)

x는 a와 m이 서로 소인 경우 반드시 존재합니다.

예를 들어, a = 3, m = 11 이라면, x는 4가 됩니다.

(3 * 4) % 11 = 1

위의 예제에서 x = 4라는 값을 찾기 위해서는 x 에 순차적으로 1부터 대입해 보면 구할 수 있지만, 시간이 많이 걸리기 때문에 다음의 방법으로 더 효율적으로 구할 수 있습니다. 

개선을 위해서 a와 m이 서로 소인 경우, 유클리드 호제법을 이용한 방법을 소개합니다.

정수 a와 b가 주어졌을 때, 각각 x, y를 곱해서 최대공약수와 x, y를 찾습니다.

a * x + b * y = gcd(a, b)

a의 m에 대한 모듈러 역수를 찾기 위해서, b를 m이라 놓고, a와 m은 서로 소이기 때문에 최대공약수를 1로 설정합니다.

a * x + m * y = 1

양변을 m으로 나눈 나머지를 취하면,

a * x + m * y ~= 1 (mod m)
a * x ~= 1 (mod m)

x는 a의 m에 대한 모듈러 역수가 됩니다.

유클리드 호제법을 이용하여 모듈러 역수를 구하는 것을 python으로 구현한 코드는 다음과 같습니다.

def modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    
    if (m == 1):
        return 0
    
    while (a > 1):
        q = a // m
        
        t = m
        
        m = a % m
        a = t
        t = y
        
        y = x - q * y
        x = t
        
    if (x < 0):
        x = x + m0
    
    return x

만약 m이 소수라면, 페르마의 소정리를 이용할 수 도 있습니다.

a ^ (m-1) ~= 1 (mod m)
a ^ (-1) ~= a ^ (m-2) (mod m)

페르마의 소정리 양변에 a ^ (-1) 을 곱하고, 좌변과 우변을 바꾸면, 우리가 찾는 모듈러 역수는 a ^ (m-2) 를 m으로 나눈 나머지가 됩니다.

기존에 사용했던 gcd 코드를 재활용해서 구현한 python 코드 입니다.

def modInverse(a, m):
    g = gdc(a, m)
    if (g != 1):
        # Inverse doesn't exist
        return -1
    else:
        return pow(a, m - 2, m)

def gcd(x, y):   
    while(y): 
        x, y = y, x % y   
    return x

정리를 해보면, a와 m이 서로 소이고, m이 소수라면 페르마의 소정리를 이용해서, 아래식으로 구하는 것이 가장 효율적이고,

a ^ (m-2) % m

m이 소수는 아니지만, a와 m이 서로 소라면 유클리드 호제법을 이용

제곱 인수가 없는 정수는 1이 아닌 제곱수를 인수로 갖지 않는 (양의) 정수를 말합니다.

쉽게 말해서 소인수 분해를 했을 때, 같은 소수가 두 개 이상 나오지 않는 정수 입니다.

다음 숫자들이 Square-free integer 들 입니다.

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113, ... (OEIS의 수열 A5117)

어떤 숫자가 Square-free number 인지 체크하는 코드 입니다.

def checkSquareFreeNumber(n):
    for i in range(2, round(n**0.5) + 1):
        if n % (i**2) == 0:
            return False
    return n

만약 특정 숫자까지 모든 값을 체크해야 한다면 아래와 같이 sieve 를 이용하는 것이 훨씬 효율적입니다.

def findSquareFreeNumbers(n):
    tArr = [True] * (n+1)
    tArr[0] = False
    tLimit = int(n**0.5) + 1
    for i in xrange(2, tLimit):
        ii = i**2
        for j in xrange(ii, n+1, ii):            
            tArr[j] = False
    tSFN = []
    for idx, value in enumerate(tArr):
        if (value):
            tSFN.append(idx)
    return tArr, tSFN

Pell's Equation 은 알고리즘 문제 풀이에 상당히 자주 등장하는데요,  아래와 같은 형태의 식에 대한 해법을 구하는 것입니다.

여기서 제약은 x, y, n 은 자연수이고, n이 제곱수가 되어서는 안된다는 것입니다. 

아래 링크에서 자세한 설명을 보실 수 있습니다.
https://en.wikipedia.org/wiki/Pell%27s_equation

간단한 대입만으로도 해결이 되는 경우가 있지만, n에 따라서는 답이 쉽게 나오지 않는 경우도 있습니다.

아래의 코드를 이용하면 쉽게 기본해를 구할 수 있습니다. 기본해를 이용하면 추가로 해를 구할 수도 있습니다. 

def solvePells(n):
    a, b = 0, 0
    x = int(n**0.5)
    y, z, r = x, 1, (x<<1)
    e1, e2, f1, f2 = 1, 0, 0, 1
    
    while True:
    	y = r * z - y
        z = ((n - y * y) // z)
        r = (x + y) // z
        
        t = e1
        e1 = e2
        e2 = e2 * r + t
        
        t = f1
        f1 = f2
        f2 = f2 * r + t
        
        a, b = f2, e2
        
        t = b
        b = a
        a = a * x + t
        
        if (a * a - n * b * b == 1):
        	break
    return a, b
    

Combination 은 다음 식으로 계산이 가능합니다.

nCr = n! / ((n-r)! * r!)

n, r 숫자가 커지면 결과가 너무 커져서 계산이 힘들어 집니다.

대신 계산을 끝까지 하지 않고도, 소인수 분해는 가능합니다.

아래 코드를 이용하면 됩니다.

def findPrimeFactors(n, k):
    tPrimeFactorsMap = {}
    
    # 소수인지 합성수인지 체크하기 위한 배열 - 최대 소수는 n 보다 작거나 같음
    tCompositeChecker = [True] * 2 + [False] * n
    
    for p in xrange(n + 1):
    
    	# 합성수인 경우 다음으로 넘김
        if tCompositeChecker[p]:
            continue
        
        q = p
        m = 1
        
        # 현재 소수 p가 몇 번 나오는지 체크하기 위한 변수
        tPrimeCnt = 0
        
        # 현재 체크 중인 q에 대해서 해당 소수 p가 몇 번 들어 있는지 체크하기 위한 리스트
        tPrimePowers = [0] * (n + 1)
        
        while True:
            tPrimePowers[q] = tPrimePowers[m] + 1
            
            # q 가 k 보다 작거나 같으면 분모, 해당 개수 만큼 빼줌
            if q <= k:
                tPrimeCnt -= tPrimePowers[q]
            # q 가 n - k 보타 크면 분자, 해당 개수 만큼 더해줌
            if q > n - k:
                tPrimeCnt += tPrimePowers[q]
                
            q += p
            m += 1
            if q > n:
                break
            
            # q는 p의 배수이므로 합성수
            tCompositeChecker[q] = True
            
        tPrimeFactorsMap[p] = tPrimeCnt
        
    return tPrimeFactorsMap

유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나입니다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘입니다.

재귀호출을 통해서 구하는 방법과 반복문을 통해서 구하는 방법이 있습니다.

재귀호출을 이용하는 방법입니다.

def gcd(m,n):
        if m < n:
                m, n = n, m
        if n == 0:
                return m
        if m % n == 0:
                return n
        else:
                return gcd(n, m%n)

반복문을 이용하는 방법입니다.

def gcd(x, y):   
        while(y): 
                x, y = y, x % y   
        return x 

라메의 정리에 의하면, 최대공약수를 구할 때, 소인수 분해를 이용하는 것 보다 유클리드 호제법을 이용하여 구하는 것이 훨씬 빠른 것으로 알려져있습니다.

보통 팩토리얼의 경우 숫자가 너무 커지기 때문에 정확한 값을 계산할 수 없는 경우가 많습니다.

하지만 팩토리얼 값을 소인수 분해했을 때, 지수가 어떻게 되는 지는 계산이 가능합니다.

다음 링크에서 자세한 설명을 보실 수 있습니다.

https://janmr.com/blog/2010/10/prime-factors-of-factorial-numbers/

특정 소수에 대한 지수를 계산하는 코드는 다음과 같습니다.

import math

def factorialExp(n, p):
    tRet = 0
    tVal = int(math.log(n, p))
    for i in xrange(1, tVal+1):
        tRet += n // p**i
    return tRet

소수 계산과 함께 많이 쓰이는 오일러 피 함수 입니다.

피 함수는 자신보다 작은 양수 중에서 자기 자신과의 최대 공약수가 1인 숫자가 몇 개인지를 나타냅니다.

따라서 소수 p의 경우 모든 숫자가 서로 소 이기 때문에 다음과 같이 쓸 수 있습니다.

φ(p) = p - 1

그리고 p와 q가 서로 소인 경우 다음과 같은 식이 성립합니다.

φ(pq) = φ(p)φ(q)

자세한 설명은 다음 링크를 참고하세요.

https://en.wikipedia.org/wiki/Euler%27s_totient_function

def totient(n):
    phi = int(n > 0 and n)
    for p in range(2, int(n ** .5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    if n > 1: phi -= phi // n
    return phi

수학에서 에라토스테네스의 체는 소수를 찾는 방법입니다. 고대 그리스 수학자 에라토스테네스가 발견하였습니다.

방법은 다음과 같습니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.

2. 2는 소수이므로 소수 리스트에 적어두고,

3. 자기 자신을 제외한 2의 배수를 모두 지웁니다.

4. 남아 있는 수 가운데 3은 소수 이므로 소수 리스트에 적어두고,

5. 자기 자신을 제외한 3의 배수를 모두 지웁니다.

6. 위의 과정을 반복하면 구하는 구간의 모든 소수를 찾을 수 있습니다.

다음은 파이썬을 이용한 예시이며, 소수인지를 체크할 수 있는 배열 정보와 소수 리스트를 리턴해 줍니다.

def findPrimes(n):
        tPrimes = [2]
        tArr = [True] * (n+1)
        tArr[0], tArr[1] = [False] * 2

        for i in xrange(4, n+1, 2):
                tArr[i] = False

#        for i in xrange(3, n+1, 2):
#                j = 3
#                while True:
#                        tmp = i * j
#                        if (tmp > n):
#                                break
#                        tArr[tmp] = False
#                        j += 2

        for i in xrange(3, int(n**0.5)+1, 2):
            if (tArr[i]):
                for j in xrange(i**2, n+1, 2*i):
                    tArr[j] = False

        for i in xrange(3, n+1, 2):
                if (tArr[i]):
                        tPrimes.append(i)

        return tArr, tPrimes