$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Модуларни инверз

време меморија улаз излаз
0,1 s 64 Mb стандардни излаз стандардни улаз

Миле и Тања морају да размене тајне поруке које се састоје од пуно великих бројева. Миле је желео да се додатно заштити и да те бројеве пре слања измени тако што је сваки број помножио тајним бројем \(a\) и израчунао остатак при дељењу са тајним бројем \(n\). Пошто је добар математичар, Миле зна да ће Тања лако моћи да дешифрује поруку ако зна бројеве \(a\) и \(n\) и ако су они узајамно прости и зато их је изабрао баш на тај начин и унапред их је договорио са Тањом. Напиши програм који Тањи помаже да дешифрује бројеве које јој је Миле послао.

Улаз

Са стандардног улаза се уносе бројеви \(a\) и \(n\) (\(2 \leq a, n \leq 10^9\)), за које се зна да су узајамно прости. Након тога уносе се бројеви \(x_i\) (\(0 \leq x_i < n\)), њих највише \(10\), сваки у посебном реду све до краја стандардног улаза, који представљају бројеве које је Миле добио након шифровања оригиналних бројева.

Излаз

На стандардни излаз исписати оригиналне (дешифроване) бројеве, сваки у посебном реду.

Пример

Улаз

3 5 1 2 3 4

Излаз

2 4 1 3

Објашњење

Заиста, важи да је \((3\cdot 2)\,\mathrm{mod}\,5 = 6 \,\mathrm{mod}\,5 = 1\), \((3\cdot 4)\,\mathrm{mod}\,5 = 12 \,\mathrm{mod}\,5 = 2\), \((3\cdot 1)\,\mathrm{mod}\,5 = 3 \,\mathrm{mod}\,5 = 3\) и \((3\cdot 3)\,\mathrm{mod}\,5 = 9 \,\mathrm{mod}\,5 = 4\).

Морате бити улоговани како бисте послали задатак на евалуацију.