목차

제곱수의 합

ps
링크acmicpc.net/…
출처BOJ
문제 번호1699
문제명제곱수의 합
레벨실버 2
분류

정수론

시간복잡도O(sqrt(n))
인풋사이즈n<=100,000
사용한 언어Python
제출기록31312KB / 76ms
최고기록36ms
해결날짜2021/08/14

풀이

코드

"""Solution code for "BOJ 1699. 제곱수의 합".

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

Tags: [Math]
"""

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()

,