Four Squares

• 제곱수의 합 (More Huge)의 쉬운 버전.
• 풀이는 제곱수의 합 을 참고. 여기에서는 n이 크지 않으므로, 두 제곱수의 합으로 나타낼수 있는지 여부를 나이브하게 O(sqrt(n))에 구현해도 동작한다.
  • 그리고 세 제곱수의 합으로 나타낼수 있는지 여부도, 르장드르의 세 제곱수 정리를 사용하지 않고 그냥 계산해도 충분히 빠르게 구할수 있다..
• 제곱수의 합와는 범위가 거의 비슷한 동일한 코드로 풀리는 문제이지만, 제곱수의 합와는 달리 문제에서 라그랑주의 네 제곱수 정리를 직접적으로 주었다는 점에서 (그래서 브루트포스 솔루션을 시도할수 있다는 점에서..) 난이도가 한개 더 낮게 측정되었다,

"""Solution code for "BOJ 17626. Four Squares".

- Problem link: https://www.acmicpc.net/problem/17626
- Solution link: http://www.teferi.net/ps/problems/boj/17626
"""

import math


def main():
    n = int(input())
    squares = {i * i for i in range(1, math.isqrt(n) + 1)}
    if n in squares:
        print(1)
    elif any(n - x in squares for x in squares):
        print(2)
    else:
        while n % 4 == 0:
            n //= 4
        print(4 if n % 8 == 7 else 3)


if __name__ == '__main__':
    main()