1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10722 Superlucky Numbers
*
* @author Julius Tschannerl
* @author David Leib
* @version 1.0, 05/25/2009
*
* Status : Accepted
* Runtime: 1.488
*/


import java.util.*;
import java.math.*;

public class Main {


public static void main(String[] args) {


Scanner sc = new Scanner(System.in);
int b,n;
b = sc.nextInt(); //basis
n = sc.nextInt(); //Stellenzahl

BigInteger[] l = new BigInteger[200];

while(b != 0 && n != 0){
if(n<= 0)
System.out.println("0");
if(n==1)
System.out.println(b-1);
else{
BigInteger B = new BigInteger(b+"");
l[1] = B;

//Berechnung aller möglichen 2 stelligen Zahlen zur basis B: B2
l[2] = B.pow(2);

//bei zweistelligen eine 13 möglich: B2-1
l[2] = l[2].subtract(new BigInteger(1+""));

//um 2-stelligen Zahlen mit führenden Nullen loszuwerden, muss die Basis abgezogen werden
//daraus kann man alle 3-stelligen Zahlen ohne 13 ausrechnen.
//man nimmt das ergebnis für die 2-stelligen, multipliziert es mit der Basis, für die zusätzliche stelle.
//dann subtrahiert man alle möglichkeiten für 2-stellige Zahlen mit führenden nullen aber ohne 13 (den man zwei schritte davor abgetogen hat)
//um 3-stellige mit führenden nullen auszuschlie�en.
//2-stellige mit führenden nullen werden mit abgezogen, da damit die 1 ausgeschlossen wird, die eine zusätzliche 13 verursachen könnte:
//daraus ergibt sich eine rekursive formel: F_n = F_n-1 - F_n-2
//das wird soooft wiederholt, bis die Stellenanzahl des inputs erreicht wird.
for(int i = 3; i<=n;i++){
l[i] = l[i-1].multiply(B);
l[i] = l[i].subtract(l[i-2]);
}

//vor Ausgabe noch rekursionssubtraktion ausführen.
System.out.println(l[n].subtract(l[n-1]));
}
b = sc.nextInt();
n = sc.nextInt();
}
}

}


2.

/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10722 (Super Lucky Numbers)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1663
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 05/29/2009
*
* Status : Accepted
* Runtime: 1.248
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.TreeMap;
import java.util.StringTokenizer;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

// StringBuilder fr die Ausgabe
StringBuilder output = new StringBuilder();

StringTokenizer token;
// Basis
int b;
// Anzahl der Stellen
int n;

Main lucky = new Main();

// Cache zum speichern bereits berechneter Werte
lucky.cache = new TreeMap<Integer, BigInteger>();

while(true){

// Die beiden Werte auslesen
token = new StringTokenizer(reader.readLine());
b = Integer.parseInt(token.nextToken());
n = Integer.parseInt(token.nextToken());

// Abberechen wenn beide Werte 0 sind
if(n==0 && b==0)break;

// Cache leeren
lucky.cache.clear();
// Anzahl an die Ausgabe anhngen
output.append(lucky.luckyNumbers(b, n));
output.append("\n");

}
System.out.print(output);
}

// Cache fr bereits berechnete Werte
TreeMap<Integer, BigInteger> cache;

/* Anzahl der SuperLuckyNumbers rekursiv berechnen.
*
*/
BigInteger luckyNumbers(int b, int n){

if(n==1){
return BigInteger.valueOf(b-1);
}

if(n==2){
return BigInteger.valueOf(b*b-b-1);
}

// Prfen ob der Wert bereits berechnet wurde
if(cache.containsKey(n))return cache.get(n);

// Berechnen und im cache speichern
BigInteger result = BigInteger.valueOf(b).multiply(luckyNumbers(b, n-1)).subtract(luckyNumbers(b, n-2));

cache.put(n, result);

return result;
}
}



3.



/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem: Super Lucky Numbers (10722)
* @author Christian Mitterreiter
* @author Rolf Luigs
* @version 1.0, 06/07/2009
* Status : Accepted
* Runtime: 2.412
*/


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


public class Main {


static HashMap<BigInteger, BigInteger> res = new HashMap<BigInteger, BigInteger>(); //Map fr Ergebnisse

public static BigInteger calc(BigInteger b, BigInteger n) {
BigInteger zwei = new BigInteger("2");
BigInteger ergebnis;

if (n.equals(BigInteger.ONE)) return (b.subtract(BigInteger.ONE));
if (n.equals(zwei)) return (b.pow(2).subtract(b).subtract(BigInteger.ONE));

if(res.containsKey(n)) return res.get(n); //wenn Zahl schon in der Map ist, rckgabe der Zahl, andernfalls berechnen

ergebnis = (b.multiply(calc(b, n.subtract(BigInteger.ONE))).subtract(calc(b, n.subtract(zwei))));

res.put(n, ergebnis); //abspeichern der berechneten Zahl
return ergebnis;
}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

BigInteger b = sc.nextBigInteger(); //einlesen der Zahlen
BigInteger n = sc.nextBigInteger();

while(!b.equals(BigInteger.ZERO) || !n.equals(BigInteger.ZERO)) {

System.out.printf("%d%n",calc(b, n)); //Ausgabe
res.clear(); //zurcksetzen der Map

b = sc.nextBigInteger();
n = sc.nextBigInteger();
}
}
}