[PROJECT_EULER] 64. Odd period square roots

time_series.csv

10.87MB

   문제는 이곳에서 확인할 수 있다.

   모든 square root는 주기를 갖는 분수 꼴로 나타낼 수 있다고 한다. 문제의 예시와 같이 square root의 주기를 반환하는 함수를 작성하여 문제를 풀었지만 주석의 why? 부분은 왜 그것이 보장되는지 모르겠다.

import math

def f(k, a, b):
    '''
        b/(sqrt(k) - a) to C + (sqrt(k) - A)/B
        
        return A, B, C
    '''
    d = (k - a ** 2)/b

    assert int(d) == d  # why?

    d = int(d)

    _a = [_a for _a in range(math.ceil(math.sqrt(k) + a - d), math.floor(math.sqrt(k) + a) + 1) if _a % d == 0]

    assert len(_a) == 1  # why?

    _a = _a[0]

    return _a - a, d, _a // d 

ans = 0

for k in range(2, 10000+1):

    a = math.floor(math.sqrt(k))
    b = 1

    if a ** 2 == k:
        continue

    perm = []

    while True:
        a, b, c = f(k, a, b)
        
        _key = f'{a}_{b}'
        
        if _key in perm:
            ans += 1 if len(perm) % 2 == 1 else 0
            break

        perm.append(_key)
ans

   답은 1322이다.