# Zkouška C++ 1. 6. 2026

Najděte všechny kořeny polynomu nad modulární aritmetikou (komutativním okruhem) $Z_m=(\{0,\dots,m-1\},\oplus,\otimes)$, kde $m \in \{2,\dots,2^{32}-1\}$, definovanou (zde pomocí C++ operátorů) jako:

$$a \oplus b = (a + b) \mathbin{\%} m$$
$$a \otimes b = (a * b) \mathbin{\%} m$$

Číslo $m$ a tudíž i výsledky operátorů $\oplus$ a $\otimes$ budou vždy reprezentovatelné typem `std::uint_fast32_t`, pro výpočet násobení, sčítání i následného modulo je však nutné použít `std::uint_fast64_t`.

Číslo $m$ (decimálně) a polynom jsou zadány na první řádce standardního vstupu, odděleny bílými znaky.

Polynom je zadán jako libovolný výraz obsahující:
- proměnnou $x$
- decimální konstanty v rozsahu $\{0,\dots,m-1\}$
- symboly `+` a `*` reprezentující $\oplus$ a $\otimes$
- závorky

Symbol `*` má vyšší prioritu než `+`, podobně jako v C++.

Například tento vstup:
```text
1001 5+x*(3+2*x*(2+x))
```
specifikuje polynom $5 \oplus 3x \oplus 4x^2 \oplus 2x^3$ nad $Z_{1001}$.

Předpokládá se hledání kořenů hrubou silou, tedy vyhodnocením zadaného polynomu pro všechna $x \in \{0,\dots,m-1\}$.

Hledání hrubou silou vyžaduje efektivní reprezentaci polynomu; např. opakovanou analýzu textového vstupu pro každé $x$ nelze stihnout v zadaných časových mezích pro velká $m$. Není však nezbytně nutné konvertovat výraz do kanonického tvaru polynomu, vhodná reprezentace původního výrazu může být dostatečně rychlá.

Program vypíše (na standardní výstup) kořeny v rostoucím pořadí, každý na zvláštní řádce a opatřený prefixem `x=`. Na závěr vypíše celkový počet kořenů opatřený prefixem `n=`.

Pro vstup z příkladu výše je očekávaný výstup tento:
```text
x=393
x=939
n=2
```