만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

나머지의 합

면접 대비

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

요약
2 이상의 정수로 이루어진 다중집합 K가 주어지고, S_K(1)부터 S_K(N)까지의 값으로 K를 복원하는 문제입니다.
난이도

보통10점 중 5점

유형
정수론, 수학, 구현
정답자
아직 제출이 없습니다

문제

중복 원소를 가질 수 있는 다중집합 KK가 주어지며, KK의 모든 원소는 2 이상의 정수다. 음이 아닌 정수 nn에 대해 나머지 합 함수 SKS_K를 다음과 같이 정의한다.

SK(n)=∑k∈K(n mod k)S_K(n) = \sum_{k \in K} (n \bmod k)

예를 들어 K={2,5,5,11}K = \{2, 5, 5, 11\}이면

SK(23)=23 mod 2+23 mod 5+23 mod 5+23 mod 11=1+3+3+1=8S_K(23) = 23 \bmod 2 + 23 \bmod 5 + 23 \bmod 5 + 23 \bmod 11 = 1 + 3 + 3 + 1 = 8

이다. 어떤 KK에 대해서도 SK(0)=0S_K(0) = 0이다.

KK는 알려지지 않았고, nn이 11부터 NN까지일 때의 SK(n)S_K(n) 값이 주어진다. 이 값들로부터 KK를 복원하는 프로그램을 작성하라.

입력

첫 줄에 정수 NN (1≤N≤1001 \le N \le 100)이 하나 주어진다. 이어지는 줄에는 SK(1),…,SK(N)S_K(1), \ldots, S_K(N) 값 NN개가 공백으로 구분되어 주어진다. 한 줄에 10개씩 나오며, 마지막 줄은 그보다 적을 수 있다.

출력

공백으로 구분된 정수를 한 줄에 출력한다. 첫 번째 값은 다중집합 KK의 원소 개수 mm이다. 그 뒤에 KK의 원소 mm개를 오름차순으로 출력한다. 같은 값이 KK에 여러 번 들어 있으면 그 횟수만큼 반복해서 출력한다.

예제2

  1. 예제 1

    입력
    16
    4 6 10 12 6 8 12 14 18 10
    3 5 9 11 5 7
    
    예상 출력
    4 2 5 5 11
    
  2. 예제 2

    입력
    20
    3 6 6 9 12 6 2 5 5 8
    11 5 8 4 4 7 10 4 7 10
    
    예상 출력
    3 3 6 7