1.

package sem2.am.bigmod;

/**
* Angewandte Mathematik, SS11
* Problem: 374 - Big Mod
* Link: http://uva.onlinejudge.org/external/3/374.pdf
*
* @author Florian Stein
* @author Franz Sommer
* @version 1.0, 04/24/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.124
*/

import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

public static void main(String[] args) throws IOException {
// input reader
Scanner scanner = new Scanner(System.in);

BigInteger b, p, m, number;

while (scanner.hasNext()) {
b = BigInteger.valueOf(scanner.nextInt());
p = BigInteger.valueOf(scanner.nextInt());
m = BigInteger.valueOf(scanner.nextInt());
number = modexp(b, p, m);
System.out.println(number);
}

}

public static BigInteger modexp(BigInteger m, BigInteger e, BigInteger n) {
int k = e.bitLength();
BigInteger s = BigInteger.ONE;
for (int i = k - 1; i >= 0; i--) {
s = s.multiply(s).mod(n);
if (e.testBit(i))
s = s.multiply(m).mod(n);
}
return s;
}
}

2.

/**
* Angewandte Mathematik, SS11
* Problem: 374 Big Mod
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=310
* @author Brielbeck, Daniel
* @author Weber, Georg
* @version 1.0, 04/12/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.116
*/
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()) {
long b = Long.parseLong(sc.nextLine());
long p = Long.parseLong(sc.nextLine());
long m = Long.parseLong(sc.nextLine());
if (sc.hasNextLine()) sc.nextLine();

System.out.println(bigmod(b,p,m));
}
}

public static long bigmod(long b, long p, long m) {
if (p == 0) return 1;
else if ((p % 2) == 0) return square(bigmod(b,p/2,m)) % m;
else return ((b % m) * bigmod(b, (p-1), m)) % m;
}
public static long square(long x) { return x * x; }
}


3.

import java.util.Scanner;

/**
* Angewandte Mathematik, SS11
* Problem: 374 Big Mod
* Link: http://uva.onlinejudge.org/external/3/374.pdf
*
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
* @version 1.0, 12/04/2011
*
* Method : B^P%M = (B%M)^P = ((B%M)%M)^P.
* Erkl¦rung: Um schnell voran zu kommen wird immer die 2-te Wurzel gezogen. Somit
* halbiert sich P immer um 2. Ist P ungerade so wird einmal B zwischen gespeichert.
* Beispiel: 5^17%4 = ((5*5)%4)^8 * 5 = (((5*5)%4*(5*5)%4)%4)^4 * 5 usw. wird P erneut ungerade
* so wird dies abermals zwischengesichert und gleich modulo des zwischenergebnisses berechnet.
* So werden die Zahlen klein gehalten und man kommt in ln(P) ans Ziel.
*
* Status : Accepted
* Runtime: 0.136
*/

public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int b;
int p;
int m;
int result;

while(sc.hasNextInt())
{
b = sc.nextInt();
p = sc.nextInt();
m = sc.nextInt();
b=b%m;
result = b;
int tmp = 1;

if(p == 0)
{
result = 1;
}
else if(b == 0)
{
result = 0;
}
else
{
/*
* Es wird immer die Wurzel gezogen. Falls die Potenz negativ
* ist so wird sie in tmp eingerechnet.
* Am Ende wird das Ergebnin dann noch mit tmp verrechnet.
*/
while(p>1)
{
if(p%2!=0)
{
tmp = (tmp * b)%m;
p--;
}
b = (b*b)%m;
p /= 2;
}

result = (b*tmp)%m;
}

System.out.println(result);
}
}

}


4.

/**
 * Angewandte Mathematik, SS11
 * Problem: 374 Big Mod
 * Link:
http://uva.onlinejudge.org/external/3/374.pdf
 *
 * @author Westerfield, Christopher


 * @author Gent Selmanaj
 * @author Marco Schuster
 * @version 1.0, 04/12/2011
 *
 * Method : Ad-Hoc
 * Status : Accepted
 * Runtime: 0.140
 */

import java.math.BigInteger;
import java.util.Scanner;


public class Main    {
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext())
        {
            int B = sc.nextInt();
            int P = sc.nextInt();


            int M = sc.nextInt();
            // Berechne R = B^P mod M
            int multiplier = 1;
            BigInteger R = BigInteger.valueOf(B).modPow(BigInteger.valueOf(P), BigInteger.valueOf(M));
            System.out.println(R.toString());


        }
    }
}

5.

/**Angewandte Mathematik, SS11
* Problem: 374 - Big Mod
* Link: http://uva.onlinejudge.org/external/3/374.pdf
*
* @author Ritter Marius
* @author Wende Tom
* @author Zehentbauer Stefan
* @version 2.0, 04/17/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.120
*/
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
do
{
System.out.println(scan.nextBigInteger().modPow(scan.nextBigInteger(), scan.nextBigInteger()));
}while(scan.hasNext());
}
}


6.


import java.math.BigInteger;
import java.util.Scanner;

public class Main {

/**
* Angewandte Mathematik, SS11
* Problem: 374 - Big Mod
* Link: http://uva.onlinejudge.org/external/3/374.pdf
*
* @author Pirmin Schneider
* @author Peter Weismann
* @version 1.0, 04/20/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.148
*/

public static void main(String[] args) {

/*
* Input: three integers in the order B, P, M
* Output: result R = B^P % M
*/
Scanner input = new Scanner(System.in);
BigInteger R;
BigInteger B;
BigInteger P;
BigInteger M;

while (input.hasNext()) {
B = input.nextBigInteger();
P = input.nextBigInteger();
M = input.nextBigInteger();
R = BigInteger.ZERO;
R = B.modPow(P, M);
System.out.println(R);

}

}

// static BigInteger modPow(int B, int P, int M) {
// long c = 1;
// for (int e = 1; e <= P; e++) {
// c = (c * b) % M;
// }
// return c;
// }


}

7.

/**
* Angewandte Mathematik, SS11
* Problem: 374 - Big Mod
* http://uva.onlinejudge.org/external/3/374.pdf
* @author Sebastian Stumpf
* @author Benjamin Vogt
* @version 1.0, 2011-04-16 20:30:01

*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.108
*/

import java.io.*;
import java.math.*;

public class Main
{
public static void main(String[] args)
{
try
{
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
while(true)
{
String s = input.readLine();
if(s.isEmpty())
s = input.readLine();
if(s.isEmpty())
System.exit(0);
BigInteger basis = new BigInteger(s);
BigInteger expo = new BigInteger(input.readLine());
BigInteger divisor = new BigInteger(input.readLine());
// there is a method in big integer, that exactly fits that problem, kind of cheating ;)
System.out.println(basis.modPow(expo, divisor));

}
}
catch(ArithmeticException ae){}
catch(NumberFormatException nsee){}
catch(IOException e) {}
// only after adding the catch of all Ecxeptions, I got accepted, otherwise: runtime error
catch(Exception e){}
}
}


-------------------------------
1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: ##374## Big Mod
* Link: http://uva.onlinejudge.org/external/3/374.pdf
*
* @author Felix Dietrich
* @version 1.0, 14.10.2010
*
* Method : BigInteger
* Status : Accepted
* Runtime: 0.112
*/

import java.math.BigInteger;
import java.util.Scanner;

public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);

while (sc.hasNext())
{
int B = sc.nextInt();
int P = sc.nextInt();
int M = sc.nextInt();

// calculate R = B^P mod M
int multiplier = 1;

BigInteger R = BigInteger.valueOf(B).modPow(BigInteger.valueOf(P), BigInteger.valueOf(M));

System.out.println(R.toString());
}
}

}




2.

/**
* FWP: Ausgewaehlte Probleme aus dem ACM
*
* Problem: 374 - Big Mod
* Accepted: 0.120
* @author Evgeni Pavlidis

*/

import java.io.*;
import java.util.*;

class Main {

/**
* Recursively calculates the b^p mod m
*/
public static long exp(long b,long p,long m)
{
if(p==0)
return 1;

if(p==1)
return b % m;

long tmp = exp(b, p / 2, m) % m;
tmp = (tmp * tmp) % m;

if(p % 2 == 0)
return tmp;

return tmp * b % m;
}


public static void main(String...args)
{
long b,p,m;
Scanner scanner = new Scanner(System.in);

while(scanner.hasNextInt())
{
b = scanner.nextInt();
p = scanner.nextInt();
m = scanner.nextInt();

System.out.println(exp(b,p,m));
}
}
}