A. Үнээнүүд ба модулийн анхны язгуур

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Үнээнүүд модулийн анхны язгуур гэж юу болохыг дөнгөж мэдээд байлаа. $p$ анхны тоо өгөгдвөл модулийн анхны язгуур нь $p$-д хуваагддаг $x-1, x^2-1, ... , x^{p-2}-1$ бүхэл тоонуудад харьяалагддахгүй $x$ ($1 ≤ x < p$) бүхэл тоо юм.

Харамсалтай нь модулийн анхны язгуурыг тооцоолоход цаг их шаарддаг учир үнээнүүдэд чиний тусламж хэрэгтэй байна. Өгөгдсөн $p$ анхны тооны модулийн анхны язгуур хэд байдгыг олоход үнээнүүдэд туслаарай.

Оролт

Оролт нь $p$ ($2 ≤ p < 2000$) бүхэл тоо бүхий ганц мөр байна. $p$ нь анхны тоо байна.

Гаралт

Гаралтанд модулийн анхны язгуур -н тоо бүхий ганц мөр байна.

Орчуулсан: Батхишиг

Жишээ тэстүүд

Оролт
3
Гаралт
1
Оролт
5
Гаралт
2

Тэмдэглэл

The only primitive root is $2.$

The primitive roots are $2$ and $3.$

Сэтгэгдлүүдийг ачааллаж байна...