사용자 도구

사이트 도구


ps:problems:boj:17626

Four Squares

ps
링크acmicpc.net/…
출처BOJ
문제 번호17626
문제명Four Squares
레벨실버 3
분류

정수론

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

풀이

  • 제곱수의 합 (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()

토론

댓글을 입력하세요:
W D R B N
 
ps/problems/boj/17626.txt · 마지막으로 수정됨: 2023/03/20 14:39 저자 teferi