#UVa：10006－Carmichael Numbers

先確認是否為質數，再去做Carmichael Number的檢查。需要的知道的知識就是底下這個式子：
\(
a^d\bmod{n} = \begin{cases}
(a^{d/2}\bmod{n} * a^{d/2}\bmod{n})\bmod{n} & \text{if d is even} \\
((a^{\left\lfloor d/2 \right\rfloor}\bmod{n} * a^{\left\lfloor d/2 \right\rfloor}\bmod{n})\bmod{n} * a) \bmod{n} & \text{if d is odd}
\end{cases}
\)

C++(0.242)

/*******************************************************/
/* UVa 10006  Carmichael Numbers                       */
/* Author: LanyiKnight [at] knightzone.studio             */
/* Version: 2015/01/08                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

long long int mod(long long int n, long long int a, long long int maxN){
  if( n == 0 ) return 1;
  if( n == 1 ) return a;

  long long int modValue = mod(n/2, a, maxN);
  if( n % 2 == 0 ){
    return (modValue * modValue) % maxN;
  }
  else {
    return ((modValue * modValue) % maxN) * a % maxN;
  }
}

bool checkCarmichael(int n, int a){
  if( mod( (long long int)n, (long long int)a, (long long int)n ) == a ){
    return true;
  }
  else {
    return false;
  }
}

int main(){
  bool composite[65005] = {true, true, false};
  for( int i = 2 ; i <= 65000 ; ++i ){
    if( !composite[i] ){
      for( int j = i+i ; j <= 65000 ; j += i ){
        composite[j] = true;
      }
    }
  }

  int n;
  while( scanf("%d", &n) != EOF && n != 0 ){
    bool isCarmichael = true;
    if( !composite[n] ) {
      isCarmichael = false;
    }

    for( int i = 2 ; i < n && isCarmichael ; ++i ){
      isCarmichael = isCarmichael && checkCarmichael(n, i);  
    }

    if( isCarmichael ){ 
      printf("The number %d is a Carmichael number.\n", n);
    }
    else{
      printf("%d is normal.\n", n);
    }
  }
  return 0;
}