UVa 10006

From Algorithmist
Jump to: navigation, search

10006 - Carmichael Numbers[edit]

Summary[edit]

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

Explanation[edit]

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

Optimizations[edit]

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.

Input[edit]

1729
17
561
1109
431
0

Output[edit]

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

Solutions[edit]

C++: http://codealltheproblems.blogspot.com/2015/06/uva-10006-carmichael-numbers.html