Fişierul intrare/ieşire:secvente3.in, secvente3.outSursăProsoft@NT 2016, Clasa a 10-a
AutorPaul DiacAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test0.25 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Secvente3

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.

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 ≤ 104
  • 1 ≤ st ≤ 106
  • 0 < dr ≤ 107, pentru orice întrebare
  • 1 < a < b < P ≤ 109
  • 0 < S ≤ 1015
  • 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)

Exemplu

secvente3.insecvente3.out
2 3 7 2
2 15
4 8
4 5

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?