아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

묘지 설계

면접 대비

시간 제한2초메모리 제한64 MB

요약
제곱의 합이 주어진 n(최대 10^14)이 되는 연속한 양의 정수 구간을 모두 찾아, 각 구간을 가장 작은 값 순서로 출력한다.
난이도

보통10점 중 6점

유형
투 포인터, 수학, 누적 합, 이분 탐색
정답자
아직 제출이 없습니다

문제

조지 왕은 왕실 묘지를 새로 설계하기로 했다. 묘지는 여러 개의 구역으로 이루어지며, 각 구역은 무덤이 정사각형으로 배치된 블록이어야 한다. 서로 다른 두 구역의 무덤 수는 모두 달라야 한다.

점성술사와 상의한 끝에, 왕은 각 구역의 한 변의 길이가 연속된 양의 정수들이어야 한다고 정했다. 한 변의 길이가 ss인 구역에는 s2s^2개의 무덤이 들어간다.

왕은 묘지에 들어갈 무덤의 총 개수 nn을 추정했고, 이 조건들을 만족하는 모든 묘지 설계를 알고 싶어 한다. 가능한 모든 설계를 찾아라.

입력

정수 nn이 하나 주어진다. 묘지에 배치할 무덤의 총 개수이다 (1≤n≤10141 \le n \le 10^{14}).

출력

첫째 줄에 가능한 묘지 설계의 개수 kk를 출력한다. 이어지는 kk개의 줄에는 각 설계를 하나씩 출력하는데, 각 줄은 그 설계에 포함된 구역의 개수 ll로 시작하고, 그 뒤에 ll개의 구역 한 변의 길이(연속된 양의 정수)를 출력한다. 설계는 가장 작은 변의 길이가 커지는 순서(즉, 구역 수가 많은 것부터 적은 것 순서)로 출력한다.

힌트

아래 그림은 n=29n = 29인 경우(첫 번째 예제)의 묘지 설계를 나타낸다.

예제2

  1. 예제 1

    입력
    29
    
    예상 출력
    1
    3  2 3 4
    
  2. 예제 2

    입력
    2030
    
    예상 출력
    2
    4  21 22 23 24
    3  25 26 27