Fişierul intrare/ieşire:pocnitoare.in, pocnitoare.outSursăONIS 2015, Runda 1
AutorMurtaza AlexandruAdăugată deThe_Viper_The_Mountain_And_The_ImpUNIBUC Impaler-009 Challenge costyv87 The_Viper_The_Mountain_And_The_Imp
Timp execuţie pe test5 secLimită de memorie4608 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Por Costel si Pocnitoarea

Într-o seară, Por Costel, cel mai vestit dintre porci, a ieşit la plimbare. Mergea liniştit pe trotuar când lângă el s-a declanşat o pocnitoare. Ca orice porc, a avut reacţia defensivă de a începe sa guiţăie disperat şi să fugă de-alungul trotuarului.

Deşi mişcarea lui Por Costel de-alungul trotuarului pare aleatoare, la o inspecţie amănunţită observăm o anumită regulă. Sa consideram strada divizată în poziţii indexate de la 0 la N-1. Por Costel se află la momentul 1 în poziţia X_1. Dacă la momentul i, Por Costel se află la poziţia X, la momentul i+1 Por Costel se va afla la poziţia (i*X + A) mod N.

Pentru a fi pregătiţi de situaţia în care Por Costel sare panicat în mijlocul străzii (Doamne fereşte !), fanii lui vă imploră sa puteţi spune în orice moment în ce poziţie se află el. Un query q semnifică întrebarea "Pe ce poziţie se află Por Costel la momentul de timp q?" Query-urile vor fi la fel de aleatoare ca şi mişcarea lui Por Costel. Vouă vi se va da query-ul iniţial Q_1 iar celelalte query-uri se generează astfel: dacă tocmai am răspuns la întrebarea Q_i, query-ul Q_i_+_1 va fi (i*X_i + B) mod (10^7 + 3) + 1 unde X_i este răspunsul la query-ul i.

Date de intrare

În fişierul de intrare pocnitoare.in se va găsii pe prima linie N, A, B, X_1 (poziţia iniţială a lui Por Costel), Q (numărul de query-uri), Q_1(query-ul iniţial).

Date de ieşire

În fişierul de ieşire pocnitoare.out se vor găsii Q linii, pe linia i aflându-se răspunsul la al i-lea query.

Restricţii

  • 1N, A, B2 * 10^9
  • 0X_1N-1
  • 1Q10^5^
  • 1Q_1(10^7 + 3)
  • a mod b reprezintă restul împărţirii lui a la b
  • Atenţie la limita de memorie!

Exemplu

pocnitoare.inpocnitoare.out
17 3 7 1 3 1
1
14
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content