Iacob Tudor (IacobTudor) Cerința
Anual, Imperiul Interstelar organizează o întâlnire administrativă în capitală. La întâlnire sunt invitați toți guvernatorii planetelor din imperiu. Planetele imperiului pot fi numerotate cu valori de la 0 la MOD-1(inclusiv) unde planeta 0 este chiar capitala. Distanțele mari dintre planete fac transportul obișnuit între planete aproape imposibil. Din fericire, găuri de vierme conectează tot imperiul. Vom nota planeta către care duce o gaură de vierme cu f(x) = (x * a + b) % MOD. Astfel, de la planeta x există un drum către planeta f(x) și un drum de la planeta f(x) la planeta x. Fiecare guvernator începe de pe o planetă cunoscută și trebuie să ajungă în capitală. Atenție, pozițiile inițiale nu trebuie să fie distincte! Fiecare salt printr-o gaură de vierme consumă o unitate de energie din rețeaua centrală. Se presupune că fiecare guvernator ia ruta cea mai scurtă către capitală. Din motive birocratice, sunteți rugați să calculați cantitatea de energie consumată de transportul guvernatorilor către captială.
Date de intrare
Pe prima linie a fișierului de intrare vor fi numerele n, a, b, MOD separate printr-un spațiu. Pe următoarea linie veți găsi n valori din intervalul [0 , MOD-1] reprezentând planeta de pe care își începe drumul fiecare guvernator.
Date de ieșire
În fișierul de ieșire trebuie să se găsească un singur număr, energia totală consumată.
Restricții și precizări
• N <= 50 , MOD <= 10^10 , 1 < a < MOD și 0 <= b < MOD
• MOD este un număr prim
• Pentru 30 de puncte , N <= 1.000.000 și MOD <= 1.000.000
• Pentru restul de 70 puncte se respectă restricțiile inițiale
• Toate numerele din fișierul de input sunt naturale.
bir_interstelara.in
2 2 1 13
bir_interstelara.out
3
Explicație
Pentru exemplul dat , cantitatea de energie este 3 , deoarece primul guvernator se poate duce prima dată pe
planetă 1 deoarece f(1) = (2*1+1)%13 = 3 și apoi se poate duce în capitală , deoarece f(0) = (2*0+1)%13 = 1. Al doilea guvernator se poate duce direct în captiala , deoarece f(6) = (2*6+1)%13 = 0.Consumul de energie este astfel 2+1 = 3.