UVa 10006

From Algorithmist
Jump to navigation Jump to search

10006 - Carmichael Numbers[edit]

Summary[edit]

Follow the instructions, and realize that you can compute in time, and without needing BigNum. The rest is simple.

Explanation[edit]

The key is realizing that you can compute in time, and without needing BigNum. This means for a given , the total complexity is . (Note that the actual complexity relative to the input size is ) For small '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