Preparing NOJ

Periodic Ruler

2000ms 1048576K

Description:

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.

Input:

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:

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.

Sample Input:

3
-1 1
1 2
2 1

Sample Output:

2 3

Sample Input:

5
1 1
2 1
3 1
4 1
5 1

Sample Output:

4 14

Sample Input:

1
1000000000 100

Sample Output:

0 0

Info

CodeForces Gym

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

Nothing Yet