//==========================================================C
//  Speed test program for A^B (mod N)                      C
//    A,B,N are 32 bits positive integer                    C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/04/05              C
//        ( JAMSTEC ES Adviser & Waseda University )        C
//==========================================================C
#include <stdio.h>
#include <math.h>
#include <time.h>
typedef signed int i32;
typedef unsigned int u32;
typedef signed long long int i64;
typedef unsigned long long int u64;
//==========================================================C
//  Compute A*B (mod P) with int                            C
//    A,P are 32 bits and B is 64 bits integer              C
//----------------------------------------------------------C
//    A       int,  In,  First input value                  C
//    B       long, In,  Second input value                 C
//    P       int,  In,  Input value of Mod                 C
//    return  int,  Out, Compute A^B (mod P)                C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/04/05              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
static i32 ModMul(i32 A, i64 B, i32 P)
 { i32 C;
   C = (i32)( ((i64)A*B) % P);
   return C;
 }
//==========================================================C
//  Compute A^B (mod P) with int                            C
//    High speed method by 2,2^2,2^4,2^8,... multiply       C
//    A,P are 32 bits and B is 64 bits integer              C
//----------------------------------------------------------C
//    A       int,  In,  Input value of Base                C
//    B       long, In,  Input value of Exponent            C
//    P       int,  In,  Input value of Mod                 C
//    return  int,  Out, Compute A^B (mod P)                C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/03/28              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
i32 ModPow1(i32 A, i32 B, i32 P)
 { i32 C = 1, AW, BW;
   AW = A;  BW = B;
   while (BW > 0)
     { if((BW&1) == 1) { C = ModMul(C, AW, P); }
       AW = ModMul(AW, AW, P);            // AW=AW^2 (mod P)
       BW = BW >> 1;                      // BW=BW/2
     }
   return C; 
 }
//==========================================================C
//  Compute A^B (mod P) with int                            C
//    A,P are 32 bits and B is 64 bits integer              C
//----------------------------------------------------------C
//    A       int,  In,  Input value of Base                C
//    B       long, In,  Input value of Exponent            C
//    P       int,  In,  Input value of Mod                 C
//    return  int,  Out, Compute A^B (mod P)                C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/03/28              C
//        ( Tokyo Kougei University )                       C
//==========================================================C
i32 ModPow2(i32 A, i32 B, i32 P)
 { i32 k, C = 1;
   for (k=0; k<B; k++)
     { C = ModMul(A, C, P); }
   return C;
 }
//==========================================================C
//  Speed test program for A^B (mod N)                      C
//    A,P are 32 bits and B is 64 bits integer              C
//----------------------------------------------------------C
//    Written by Yasunori Ushiro ,  2011/04/05              C
//        ( JAMSTEC ES Adviser & Waseda University )        C
//==========================================================C
i32 main()
 { i32 A, P, C, D, b;
   i64 B, T1, T2;
   double CPU;
// Initial set
   printf("input A,P for A^B (mod P)\n");
   scanf("%d %d",&A,&P);
   printf("input b (B=b*1000000) for A^B (mod P)\n");
   scanf("%d",&b);
   printf("Compute C=A^B (mod P)\n");
   B = (i64)b*1000000;
   printf(" A=%d, b=%d(B=b*1000000), P=%d\n",A,b,P);
// High speed C=A^B (mod P)
   T1 = clock();
   C = ModPow1(A, B, P);
   T2 = clock();
   CPU = (double)(T2 - T1)/CLOCKS_PER_SEC;
   printf("  High speed modpow; C=%d",C);
   printf(", Time(s)=%7.3f\n",CPU);
// Low speed C=A^B (mod P)
   T1 = clock();
   C = ModPow2(A, B, P);
   T2 = clock();
   CPU = (double)(T2 - T1)/CLOCKS_PER_SEC;
   printf("  B times by modmul; C=%d",C);
   printf(", Time(s)=%7.3f\n",CPU);
   return 0;
 }