Fişierul intrare/ieşire:	secvente3.in, secvente3.out	Sursă	Prosoft@NT 2016, Clasa a 10-a
Autor	Paul Diac	Adăugată de	Paul Diac •diac_paul
Timp execuţie pe test	0.25 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Secvente3

Fie A_i un şir de numere naturale nenule definit astfel:

A₁ = a
A_i = (A_i-1 × b ) modulo P , pentru orice i > 1

Astfel şirul A poate fi definit de trei numere constante cunoscute: a, b şi P.

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 A _st + A _st+1 + A _st+2 + … + A _dr ≤ S ?”

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

• M ≤ 10⁴
• 1 ≤ st ≤ 10⁶
• 0 < dr ≤ 10⁷, pentru orice întrebare
• 1 < a < b < P ≤ 10⁹
• 0 < S ≤ 10¹⁵
• Pentru orice test numerele a, b şi P asigură că orice A_i este nenul
• Pentru orice întrebare A_st ≤ S
• Atentie la limita de memorie
• Atentie la folosirea long long (C++) sau int64 (Pascal)

Exemplu

Explicaţie

A = (2, 6, 4, 5, 1, 3 …)
A₂ + A₃ + A₄ = 6 + 4 + 5 = 15 ≤ 15
A₄ + A₅ = 5 + 1 = 6 ≤ 8
dar A₄ + A₅ + A₆ = 5 + 1 + 3 = 9 e deja > 8

Cum se trimit solutii?