[PROJECT_EULER] 64. Odd period square roots

time_series.csv

10.87MB

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

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

<code>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 </code>

   답은 1322이다.