Pell's Equation

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