== include(page="template/taskheader" task_id="secvente3") ==

Poveste şi cerinţă...

Fie Ai un şir de numere naturale nenule definit astfel:
 
A1 = a
Ai = (Ai-1 × b) modulo P, pentru orice i > 1
 
Astfel şirul A poate fi definit de trei numere constante cunoscute: a, b şi P.
 
h2. Cerinta
Pentru un şir cunoscut A să se raspundă la M întrebări (st, S) cu semnificaţia:
„Care este cel mai mare indice dr(≥st) astfel încât Ast + Ast+1 + Ast+2 + … + Adr ≤ S ?”

h2. Date de intrare

Fişierul de intrare $secvente3.in$ ...

Fişierul de intrare $secvente3.in$ conţine pe prima linie numerele a, b, P şi M separate prin spaţiu. Următoarele M linii contin parametrii pentru fiecare întrebare st şi S separaţi prin spaţiu.

h2. Date de ieşire

În fişierul de ieşire $secvente3.out$ ...

În fişierul de ieşire $secvente3.out$ va conţine pe prima linie M numere: răspunsurile dr la întrebări în ordine, valori separate prin spaţiu.

h2. Restricţii

* $... ≤ ... ≤ ...$

* M ≤ 104
* 1 ≤ st ≤ 106
* 1 < a < b < P ≤ 109
* 0 < S ≤ 1015
* 0 < dr ≤ 107, pentru orice întrebare
* Pentru orice test numerele a, b şi P asigură că orice Ai este nenul
* Pentru orice întrebare Ast ≤ S
* Atentie la limita de memorie
* Atentie la folosirea long long (C++) sau int64 (Pascal)

h2. Exemplu
table(example). |_. secvente3.in |_. secvente3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 3 7 2
2 15
4 8
| 4 5

|
h3. Explicaţie

...

A = (2, 6, 4, 5, 1, 3 …)
A2 + A3 + A4 = 6 + 4 + 5 = 15 ≤ 15
A4 + A5 = 5 + 1 = 6 ≤ 8
dar A4 + A5 + A6 = 5 + 1 +  3 = 9 e deja > 8
 
 
 

== include(page="template/taskfooter" task_id="secvente3") ==