Zkouška C++ 1. 6. 2026

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

a⊕b=(a+b)%ma \oplus b = (a + b) \mathbin{\%} m a⊗b=(a∗b)%ma \otimes b = (a * b) \mathbin{\%} m

Číslo mm 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 mm (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 xx

  • decimální konstanty v rozsahu {0,…,m−1}\{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:

1001 5+x*(3+2*x*(2+x))

specifikuje polynom 5⊕3x⊕4x2⊕2x35 \oplus 3x \oplus 4x^2 \oplus 2x^3 nad Z1001Z_{1001}.

Předpokládá se hledání kořenů hrubou silou, tedy vyhodnocením zadaného polynomu pro všechna x∈{0,…,m−1}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é xx nelze stihnout v zadaných časových mezích pro velká mm. 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:

x=393
x=939
n=2