CCEX Suceava 2023 - clasa a VIII-a | Sirmod

This was the problem page during the contest. Access the current page here.
Time limit: 0.3s Memory limit: 64MB Input: sirmod.in Output: sirmod.out

Enunţ

Alex a învățat la școală despre mai multe șiruri cum ar fi șirul lui Fibonacci. Mai mult, a învățat că poate să își creeze propriul său șir. După ce a făcut asta, fiind mai curios din fire, Alex a studiat mai multe proprietăți ale acestuia, precum și restul numerelor din el la împărțirea cu alte numere, dar nu își poate răspunde la toate întrebările așa că vă roagă pe voi să-l ajutați.

Cerinţe

Se dă un șir format prin relația de recurență ai=ai1x+ya_i=a_{i-1} \cdot x + y. Dându-se QQ întrebări de forma l,r,k,ml, r, k, m de forma câte numere din șirul alara_l \dots a_r dau restul kk la împărțirea cu mm, răspundeți eficient la fiecare întrebare, pentru a-l ajuta pe Alex.

Date de intrare

Fișierul de intrare sirmod.in conține pe prima linie trei numere întregi: a1,x,ya1, x, y. Pe a doua linie se va afla numărul natural qq, cu semnificația din enunț. Pe următoarele qq linii se vor afla 44 numere naturale, l,r,k,ml, r, k, m.

Date de ieşire

În fișierul de ieșire sirmod.out se vor afla qq linii, pe linia ii aflându-se un singur număr natural, reprezentândrăspunsul la întrebarea ii.

Restricţii și precizări

  • 1a1,x,y1091 \leq a_1,x,y \leq 10^9
  • 1q21051 \leq q \leq 2 \cdot 10^5
  • 1mi50001 \leq m_i \leq 5000
  • 0ki<mi0 \leq k_i < m_i
  • 1liri10181 \leq l_i \leq r_i \leq 10^{18}
    Pentru teste în valoare de 3030 de puncte: 1q100,1liri1061 \leq q \leq 100, 1 \leq l_i \leq r_i \leq 10^6
    Pentru teste în valoare de 6060 de puncte: 1q50001 \leq q \leq 5000

Exemple

sirmod.in

1 2 1
2
1 5 0 31
2 7 3 31

sirmod.out

1
2

Explicații

Primele 77 numere din șir sunt 1,3,7,15,31,63,1271,3,7,15,31,63,127

Log in or sign up to be able to send submissions!