Computer Programming Contest Preparation

    1 /* 10692 */
    2 
    3 #include <stdio.h>
    4 #include <stdlib.h>
    5 #include <math.h>
    6 
    7 #define TRUE 1
    8 #define FALSE 0
    9 #define DEBUG if(FALSE)
   10 #define MAXA 10
   11 
   12 unsigned int a[MAXA];
   13 unsigned int m, n;
   14 
   15 
   16 int getInput()
   17 {
   18     unsigned int i;
   19     if(scanf(" %u ", &m) != 1)
   20         return FALSE;
   21     DEBUG printf("m: %u\n", m);
   22 
   23     scanf(" %u ", &n);
   24     DEBUG printf("n: %u\na: ", n);
   25     for(i = 0; i < n; i++)
   26         {
   27             scanf(" %u ", &a[i]);
   28             DEBUG printf("%u ", a[i]);
   29         }
   30     DEBUG printf("\n");
   31 
   32     return TRUE;
   33 }
   34 
   35 /* should return ((unsigned int)pow(base,power)) % mod */
   36 unsigned int powmod(unsigned int base, unsigned int power, unsigned int mod)
   37 {
   38     unsigned int i = 1;
   39     unsigned int result = 1;
   40     unsigned int currentpow = base;
   41     int x;
   42     if (power == 0) return 1;
   43     if (power == 1) return base;
   44     for(x=0; x<32; x++)
   45         {
   46             if (i > power) break;
   47             if ((i & power) != 0)
   48                 {
   49                     result *= currentpow;
   50                     result %= mod;
   51                 }
   52             currentpow *= currentpow;
   53             currentpow %= mod;
   54             i <<= 1;
   55         }
   56     return result;
   57 }
   58 
   59 
   60 unsigned int process()
   61 {
   62     int i;
   63     unsigned int base, power;
   64     if(n == 1)
   65         return a[0] % m;
   66 
   67     power = powmod(a[n-2], a[n-1], m);
   68     for(i = n - 2; i > 0; i--)
   69         {
   70             base = a[i-1];
   71             power = powmod(base, power, m);
   72         }
   73     return power % m;
   74 }
   75 
   76 
   77 int main (int argc, char const *argv[])
   78 {
   79     int iteration = 0;
   80     while(getInput())
   81         printf("Case #%d: %u\n", ++iteration, process());
   82 
   83     return 0;
   84 }
   85 
   86