# UVa 10006

## Summary

Follow the instructions, and realize that you can compute ${\displaystyle a^{n}{\bmod {n}}}$ in ${\displaystyle O(\log n)}$ time, and without needing BigNum. The rest is simple.

## Explanation

The key is realizing that you can compute ${\displaystyle a^{n}{\bmod {n}}}$ in ${\displaystyle O(\log n)}$ time, and without needing BigNum. This means for a given ${\displaystyle n}$, the total complexity is ${\displaystyle O(n\log n)}$. (Note that the actual complexity relative to the input size is ${\displaystyle O(n2^{n})}$) For small ${\displaystyle n}$'s, this is good enough.

## Optimizations

Note that there are only 15 Carmichael numbers within the range given, so you can actually precalculate them and check them with a simple statement.

```1729
17
561
1109
431
0
```

## Output

```The number 1729 is a Carmichael number.
17 is normal.
The number 561 is a Carmichael number.
1109 is normal.
431 is normal.
```