h3. (problema medie, clasele 11-12)

Este evident ca o solutie care simula evaluarea expresiei nu s-ar fi incadrat ca timp sau ca memorie, deoarece rezultatele obtinute pe parcurs pot fi foarte mari, desi rezultatul final este limitat de $10^1000^$. Pentru rezolvarea acestei probleme este necesara 'teorema chineza a resturilor':http://en.wikipedia.org/wiki/Chinese_remainder_theorem :
Fie $K$ numere prime distincte $P{~1~}, P{~2~},... ,P{~K~}$ si $K$ resturi $R{~1~}, R{~2~},... R{~K~}$.
Exista un numar natural unic $N$ mai mic decat produsul celor $K$ numere prime care satisface relatiile $N = R{~i~} (mod P{~i~})$.
Vom rezolva intai problema de $70%$, adica variabilele si rezultatul sunt numere naturale. Daca alegem un numar suficient de numere prime astfel incat produsul lor sa fie mai mare decat $10^1000^$, putem calcula rezultatul expresiei modulo fiecare numar prim in timp liniar si putem reconstitui rezultatul (care va fi unic) folosind teorema chineza a resturilor. O prezentare detaliata a acestei teoreme se gaseste si in 'acest articol':downloads?action=download&file=mate.pdf.
Putem reduce varianta cu numere intregi la problema initiala cu numere naturale adunand constanta $10^1000^$ la expresie. Astfel se garanteaza ca rezultatul expresiei este in intervalul $[0, 2*10^1000^]$.
Deoarece lungimea expresiei este de $100.000$ trebuiau se se foloseasca numere prime relativ mari. Solutia oficiala foloste aproximativ $120$ de numere prime din intervalul $[10^9^, 2*10^9^]$.
 

h2. 'Obiective':problema/obiective
h3. (problema grea, clasele 11-12)