TLE '17 Contest 5 P3 - Willson and Factorization

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
PyPy 2 3.0s
PyPy 3 3.0s
Python 2 4.0s
Python 3 4.0s
Memory limit: 256M

Author:
Problem types
Willson is sad because nobody likes him.

Willson the Canada Goose is like any other Canada Goose - he suspects that many humans don't like him.

As a result, he challenges you to do the following problem:

Consider the set \mathbb{Z}_n = \{0,1,2,\ldots,n-1\}.

We say that an element u in \mathbb{Z}_n is a unit if there is some element v in \mathbb{Z}_n with uv \equiv 1 \pmod{n}.

We say that a non-zero, non-unit element i in \mathbb{Z}_n is irreducible if there are no elements a,b in \mathbb{Z}_n where a,b are not units and ab \equiv i \pmod{n}.

We say that a non-zero, non-unit element p in \mathbb{Z}_n is prime if for all elements a,b in \mathbb{Z}_n, if px \equiv ab \pmod{n} for some element x in \mathbb{Z}_n, then py \equiv a \pmod{n} for some element y in \mathbb{Z}_n or pz \equiv b \pmod{n} for some element z in \mathbb{Z}_n.

Given n, please output all of the units, irreducibles, and primes of \mathbb{Z}_n.

Input Specification

The only line of input will contain a single integer, n (2 \le n \le 200).

For 20\% of the points, n is prime.

For an additional 20\% of the points, n \le 15.

For an additional 20\% of the points, n \le 50.

Output Specification

Output, in numerical order, first the units, then the irreducibles, then the primes of \mathbb{Z}_n. See the Sample Output for more specific formatting.

Sample Input 1

10

Sample Output 1

Units:
1
3
7
9
Irreducibles:
Primes:
2
4
5
6
8

Sample Input 2

12

Sample Output 2

Units:
1
5
7
11
Irreducibles:
2
10
Primes:
2
3
9
10

Comments

There are no comments at the moment.