5095.Sum of Remainders

Time Limit: 1s Memory Limit: 256MB

Given a multiset (elements may be duplicates), $K$ of integers $ \ge 2$, the sum of remainders function associated with $K, S_K$ , defined on non-negative integers, $n$, is given by:

$S_K(n) = \sum(k\ in\ K\ |\ n \bmod k)$

For instance, if $K = \{2, 5, 5, 11\}$,

$S_K(23) = 23 \bmod 2 + 23 \bmod 5 + 23 \bmod 5 + 23 \bmod 11 = 1 + 3 + 3 + 1 = 8$.

Note that $S_K(0) = 0$ for any $K$.

For this problem you will write a program which takes as input the values of $S_K (n)$ for $n$ from $1$ to $N$ for some unknown multiset $K$. The program will output the number of integers in $K$ followed by the integers in $K$ in non-decreasing order.

Input Format(From the terminal/stdin)

Input consists of multiple lines. The first line contains a single decimal integer $N, (1 ≤ N ≤ 100)$, which is the number of values of $S_K (n), (1 \le n \le N)$, that follow. The following lines contain the $N$ values as space separated decimal integers, $10$ values per line (except perhaps for the last line).

Output Format(To the terminal/stdout)

There is one line of output containing a space separated sequence of decimal integers. The first value is the number, $m$, of integers in the multiset $K$. This is followed by the $m$ integers of the multiset $K$ in non-decreasing order. Note: if a value is a member multiple times, it should appear in the list that many times.

Sample Input 1

Copy
16
4 6 10 12 6 8 12 14 18 10
3 5 9 11 5 7
  \n
 · ·  ·  · · ·  ·  ·  ·  \n
 · · ·  · · \n

Sample Output 1

Copy
4 2 5 5 11
 · · · ·  \n

Sample Input 2

Copy
20
3 6 6 9 12 6 2 5 5 8
11 5 8 4 4 7 10 4 7 10
  \n
 · · · ·  · · · · · \n
  · · · · · ·  · · ·  \n

Sample Output 2

Copy
3 3 6 7
 · · · \n
Source: 2022 Great NY Regional

Submit

请先 登录

© 2025 FAQs