Preparing NOJ

Hitagi has a ruler of infinite length. It has a mark on every integer, where the mark on integer $$$i$$$ has color $$$c_i$$$. Each color is represented by an integer from $$$1$$$ to $$$100$$$.

She noticed that the ruler's color pattern repeats with a period of $$$t$$$. The period $$$t$$$ is defined by the smallest positive integer that satisfies $$$c_i = c_{i+t}$$$ for all integers $$$i$$$.

Hitagi told Koyomi the colors of $$$n$$$ marks of her choice. Koyomi wants to find all positive integers that cannot be a period of the ruler, regardless of the colors of unchosen marks. Write a program to find all such numbers, and output their count and sum.

The first line contains a single integer $$$n\ (1 \le n \le 50)$$$.

The following $$$n$$$ lines each contain two integers $$$x_i\ (|x_i| \le 10^9)$$$ and $$$a_i\ (1 \le a_i \le 100)$$$. This indicates that the integer $$$x_i$$$ is marked with the color $$$a_i$$$.

If $$$i \neq j$$$, then $$$x_i \neq x_j$$$.

Output two integers on one line. The first integer is the number of positive integers that cannot be the period of the ruler. The second integer is their sum.

3 -1 1 1 2 2 1

2 3

5 1 1 2 1 3 1 4 1 5 1

4 14

1 1000000000 100

0 0

Info

Provider CodeForces Gym

Origin XXII Open Cup. Grand Prix of Korea

Code GYM103371J

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:45:21

Related