Fișierul intrare/ieșire	tombola.in, tombola.out	Sursă	ONI 2019 baraj gimnaziu
Autor	Dana Lica	Adăugată de	Mircea Rebengiuc • mircea_007
Timp de execuție pe test	0.75 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	3.25

Vezi soluțiile trimise | Statistici

Tombola (baraj gimnaziu)

Aflat într-o vizită cu părinții, Iliuță primește un bilet la tombolă pe care este scris un număr natural S. Pentru a câștiga un premiu, Iliuță trebuie să afle, plecând de la numărul S, un număr câștigător X. Pentru a-l ajuta să ghicească numărul câștigător, mama îi spune lui Iliuță că numărul S de pe biletul său este suma dintre numărul câștigător X și toate numerele obținute plecând de la numărul câștigător X, prin ștergerea cifrei unităților numărului X, apoi, succesiv, prin ștergerea cifrei unităților numărului obținut la pasul anterior, până se ajunge la un număr de o singură cifră.

De exemplu, dacă numărul X este 2019, atunci din X se pot obține după regula de mai sus trei numere: 201, 20 și 2. Suma tuturor acestor numere este S = 2019 + 201 + 20 + 2 = 2242. Deci, dacă pe biletul lui Iliuță se află numărul S = 2242, atunci numărul câștigător corespunzător lui S este X = 2019.

Din păcate, nu toate numerele naturale permit determinarea unui număr câștigător. De exemplu, pentru numărul 21 nu există niciun număr natural X din care să putem obține 21 după regula descrisă de mama lui Iliuță.

Cu ajutorul unui program a fost generat automat un șir de N numere, numerotate în ordinea generării S₁, S₂, ..., S_N. Programul respectiv primește patru numere naturale A, B, C, D și primul număr din șir S₁. Al i-lea număr generat se obține după regula Si = ((S_i-1 % A ) * B + C) % D, unde 1 < i ≤ N, iar a % b reprezintă restul împărțirii lui a la b (b ≠ 0).

Cerință

Cunoscându-se numerele naturale N, S1, A, B, C, D, scrieți un program care rezolvă următoarele cerințe:

1. pentru fiecare dintre termenii șirului S₁, S₂, ..., S_N, determină cel mai mare număr natural mai mic strict decât termenul respectiv, pentru care există un număr câștigător; programul va afișa restul împărțirii sumei numerelor obținute la 10¹⁸ + 31;
2. pentru fiecare dintre termenii șirului S₁, S₂, ..., S_N, determină câte numere naturale mai mici sau egale cu termenul respectiv NU au număr câștigător; programul va afișa restul împărțirii sumei rezultatelor obținute la 10¹⁸ + 31.

Date de intrare

Fișierul de intrare tombola.in conținepe prima linie numărul natural p, reprezentând cerința care trebuie rezolvată (1 sau 2). Pe a doua linie se află, în această ordine, numerele naturale N S1 A B C D, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire tombola.out va conține un singur număr natural care reprezintă rezultatul la cerința p.

Restricții

• 1 ≤ N ≤ 500000
• 1 < S1, C, D ≤ 10¹⁷
• 1 < A, B, ≤ 10⁹

Exemple

tombola.in	tombola.out	Explicatii
1 1 22 3 3 3 3	20	Se rezolvă cerința 1. Avem un singur termen în șir S1 = 22. Numărul 20 este cel mai mare număr strict mai mic decât 22 care acceptă un număr câștigător ( X = 19 deoarece 20 = 19 + 1 ).
2 1 22 3 3 3 3	2	Se rezolvă cerința 2. Avem un singur termen în șir S1 = 22. Există două numere mai mici sau egale cu 22 care NU acceptă număr câștigător, 10 și respectiv 21.

tombola.in	tombola.out
1 3 12345678901234567 999999999 123456789 98765432109876543 1020304050607080	12805467424792840
2 3 98765432109876543 999999999 123456789 12345678901234567 1020304050607080	9912065223185559