Missing
Interview Problem
Time Limit: 2s, Memory Limit: 256MiB
Ели има N естествени числа A1, A2, … AN. Сега тя се чуди кое е най-малкото естествено число, което тя няма. За целите на тази задача ще считаме, че 0 е естествено число.
Вход
На единствен ред на стандартния вход ще бъдат зададени пет естествени числа N, F, P, Q, и M. N-те числата в списъка на Ели се генерират по следния начин:
  • A1 = F
  • Аi = (Ai-1 * P + Q) % M
Изход
На стандартния изход изведете едно единствено естествено число – най-малкото, което Ели няма.
Ограничения
  • 1 ≤ N ≤ 20,000,000
  • 0 ≤ F, P, Q < M ≤ 1,000,000,009
Примерен Вход Примерен Изход
15 5 19 16 23 7
20000000 705882359 1 5882353 1000000009 117647
В първия пример числата, които Ели има, са {5, 19, 9, 3, 4, 0, 16, 21, 1, 12, 14, 6, 15, 2, 8}.
Най-малкото, което липсва, е 7.
Мрън!