LCC '18 Contest 5 J4 - How Many 5s?

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Mrs. Krasteva is known to be very good at guessing the number of people in her class that get a score of 5 on the AP exam. So good in fact that she has always been correct or 1-2 students off. Everyone wants to know her current guess so she has a challenge for you.

She will give you a list of numbers in which each number on the list produces the same remainder \(R\) when dividing the unknown number of people. You will also be given the value of the remainder \(R\). She also says that the number of people is the smallest possible number greater than its divisors which satisfies these conditions.

Find the number of people that score a 5 on the AP exam!

Input Specification

The first line will contain the amount of numbers \(N\) and the shared remainder \(R\)

The next \(N\) lines will contain a number \(M\) which produces the remainder \(R\) when dividing the number of people.

Output Specification

Output the smallest number of people that score a 5 on the AP exam \(S \bmod 10^9+7\), satisfying the constraint that the number of people must not be less than \(\min{M}\).


Subtask 1 [40%]

\(N\le 10, \ R \le 100, \ M \le 100\)

Subtask 2 [30%]

\(N\le 25, \ R \le 1000, \ M \le 1000\)

Subtask 3 [30%]

\(N\le 5, \ R < 10^{10}, \ M < 10^{10}\)

Sample Input 1

2 4

Sample Output 1


Sample Input 2

5 10

Sample Output 2



  • 0
    _  commented on March 15, 2019, 10:06 p.m.

    Note: Intermediate numbers may or may not fit in a 128 bit integer.