K-th Element
Турнир за Купата на Декана, 2012
Time Limit: 2s, Memory Limit: 16MiB
Ели и Станчо получиха своята първа поръчка! Техният клиент има специфични изисквания за степента на минерализираност на водата – той иска точно K-тия по минерализираност тип от водите, които те предлагат.
Компанията на Ели и Станчо предлага N вида минерална вода, всеки от които има дадена степен на минерализираност (като е възможно повече от един вид да имат еднаква степен). Поради странния начин на производство, първият вид има стойност F, а всеки следващ се образува от предходния, като той е умножен по някаква константа A, след това е прибавено B и накрая е взет остатъка от резултата, при деление на M. Тоест, стойностите на минерализираност на водата, която предлагат, е редицата V1, V2, ..., VN, като:
Компанията на Ели и Станчо предлага N вида минерална вода, всеки от които има дадена степен на минерализираност (като е възможно повече от един вид да имат еднаква степен). Поради странния начин на производство, първият вид има стойност F, а всеки следващ се образува от предходния, като той е умножен по някаква константа A, след това е прибавено B и накрая е взет остатъка от резултата, при деление на M. Тоест, стойностите на минерализираност на водата, която предлагат, е редицата V1, V2, ..., VN, като:
- V1 = F
- V2 = (V1 * A + B) % M
- V3 = (V2 * A + B) % M
- ...
- VN = (VN-1 * A + B) % M
Вход
На единствен ред на стандартния вход ще бъдат зададени шест цели числа, разделени с интервал – K, N, F, A, B, M – позицията на търсения елемент, както и параметрите за генерирането на мултимножеството.
Изход
На стандартния изход изведете едно цяло число – стойността на К-тия по големина елемент от мултимножеството.
Ограничения
- 1 ≤ K ≤ N ≤ 20,000,000
- 1 ≤ F, A, B < M ≤ 2,000,000,000
Примерен Вход | Примерен Изход |
---|---|
5 7 3 3 1 20 | 11 |
133742 666666 13 17 1 1000003 | 199858 |
В първия пример образуваната редица е {3, 10, 11, 14, 3, 10, 11}. Петият по големина елемент в нея е със стойност 11.